Optimal External Memory Interval Management
Authors:
- Lars ArgeLALars Arge
- Jeffrey Scott VitterJVJeffrey Scott Vitter
- 1 January 2003
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 32 (6) , 1488-1508
Abstract
In this paper we present the external interval tree, an optimal external memory data structure for answering stabbing queries on a set of dynamically maintained intervals. The external interval tree can be used in an optimal solution to the dynamic interval management problem, which is a central problem for object-oriented and temporal databases and for constraint logic programming. Part of the structure uses a weight-balancing technique for efficient worst-case manipulation of balanced trees, which is of independent interest. The external interval tree, as well as our new balancing technique, have recently been used to develop several efficient external data structures.Keywords
This publication has 34 references indexed in Scilit:
- The Buffer Tree: A Technique for Designing Batched External Data StructuresAlgorithmica, 2003
- Indexing Moving PointsJournal of Computer and System Sciences, 2003
- Efficient Splitting and Merging Algorithms for Order Decomposable ProblemsInformation and Computation, 1999
- Multidimensional access methodsACM Computing Surveys, 1998
- External segment treesAlgorithmica, 1994
- The input/output complexity of sorting and related problemsCommunications of the ACM, 1988
- A new data structure for representing sorted listsActa Informatica, 1982
- On the average number of rebalancing operations in weight-balanced treesTheoretical Computer Science, 1980
- Ubiquitous B-TreeACM Computing Surveys, 1979
- Organization and maintenance of large ordered indexesActa Informatica, 1972