Optimal External Memory Interval Management

DOI10.1137/S009753970240481XzbMATHOpenAlexMaRDI QIDQ4429699FDO

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)

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

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)