Optimal External Memory Interval Management

DOI10.1137/S009753970240481XzbMath1030.68027OpenAlexW2012714839MaRDI QIDQ4429699

Lars Arge, Jeffrey Scott Vitter

Publication date: 28 September 2003

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s009753970240481x

zbMATH Keywords

data structuresstabbing queriesI/O efficientinterval management

Mathematics Subject Classification ID

Searching and sorting (68P10) Database theory (68P15) Data structures (68P05)

Related Items

I/O-efficient 2-d orthogonal range skyline and attrition priority queues ⋮ I/O-efficient dynamic planar point location ⋮ Optimal external memory planar point enclosure ⋮ Dynamic range majority data structures ⋮ Compressed Data Structures for Dynamic Sequences ⋮ EXTERNAL MEMORY ORTHOGONAL RANGE REPORTING WITH FAST UPDATES ⋮ Towards an Optimal Method for Dynamic Planar Point Location ⋮ Efficient splitting and merging algorithms for order decomposable problems ⋮ Indexing for summary queries ⋮ Compressed dynamic range majority and minority data structures ⋮ Space efficient data structures for dynamic orthogonal range counting ⋮ An (Almost) Optimal Solution for Orthogonal Point Enclosure Query in ℝ³ ⋮ Time-Optimal Top-$k$ Document Retrieval ⋮ Unnamed Item ⋮ \(D^2\)-tree: a new overlay with deterministic bounds ⋮ Dynamic Planar Range Maxima Queries ⋮ Towards optimal range medians ⋮ Unnamed Item ⋮ Dynamic path queries in linear space ⋮ Orthogonal range searching in linear and almost-linear space ⋮ Unnamed Item ⋮ A LINEAR SPACE DATA STRUCTURE FOR ORTHOGONAL RANGE REPORTING AND EMPTINESS QUERIES ⋮ Intersection joins under updates ⋮ External memory planar point location with logarithmic updates ⋮ Compressing dictionary matching index via sparsification technique