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

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

zbMATH Keywords

data structuresstabbing queriesI/O efficientinterval management

Mathematics Subject Classification ID

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

Cited In (27)

• Towards an Optimal Method for Dynamic Planar Point Location
• 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
• EXTERNAL MEMORY ORTHOGONAL RANGE REPORTING WITH FAST UPDATES
• An (Almost) Optimal Solution for Orthogonal Point Enclosure Query in ℝ³
• Compressed Data Structures for Dynamic Sequences
• Title not available (Why is that?)
• Compressing dictionary matching index via sparsification technique
• Dynamic range majority data structures
• Efficient splitting and merging algorithms for order decomposable problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• Time-Optimal Top-$k$ Document Retrieval
• 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
• Compressed dynamic range majority and minority data structures
• I/O-efficient dynamic planar point location
• 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)