Optimal External Memory Interval Management

DOI10.1137/S009753970240481XzbMATH Open1030.68027OpenAlexW2012714839MaRDI QIDQ4429699FDOQ4429699

Authors 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

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

Recommendations

• On the dynamic one-dimensional interval management problem in external memory
• Publication:4490352
• An optimal dynamic data structure for stabbing-semigroup queries
• The buffer tree: A new technique for optimal I/O-algorithms
• scientific article; zbMATH DE number 1792106

Cited In (27)

• I/O-efficient 2-d orthogonal range skyline and attrition priority queues
• Optimal external memory planar point enclosure
• On the dynamic one-dimensional interval management problem in external memory
• Towards optimal range medians
• Orthogonal range searching in linear and almost-linear space
• An (Almost) Optimal Solution for Orthogonal Point Enclosure Query in ℝ³
• Compressed Data Structures for Dynamic Sequences
• Title not available (Why is no real title available?)
• Compressing dictionary matching index via sparsification technique
• Time-optimal top-\(k\) document retrieval
• Dynamic range majority data structures
• Efficient splitting and merging algorithms for order decomposable problems
• Title not available (Why is no real title available?)
• Towards an optimal method for dynamic planar point location
• Dynamic Planar Range Maxima Queries
• Dynamic path queries in linear space
• A LINEAR SPACE DATA STRUCTURE FOR ORTHOGONAL RANGE REPORTING AND EMPTINESS QUERIES
• \(D^2\)-tree: a new overlay with deterministic bounds
• External memory fully persistent search trees
• External memory orthogonal range reporting with fast updates
• Compressed dynamic range majority and minority data structures
• I/O-efficient dynamic planar point location
• Dynamic planar orthogonal point location in sublogarithmic time
• Intersection joins under updates
• External memory planar point location with logarithmic updates
• Indexing for summary queries
• Space efficient data structures for dynamic orthogonal range counting

This page was built for publication: Optimal External Memory Interval Management

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4429699)