Optimal External Memory Interval Management

View/ Open
Issue Date
2003Author
Arge, Lars
Vitter, Jeffrey Scott
Publisher
Society for Industrial and Applied Mathematics
Type
Article
Article Version
Scholarly/refereed, publisher version
Metadata
Show full item recordAbstract
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 usedin an optimal solution to the dynamic interval management problem, which is a central problem for object-orientedandtemp oral databases andfor 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.
Description
AMS subject classifications. 68P05, 68P10, 68P15
DOI. 10.1137/S009753970240481X
Collections
Citation
L. Arge and J. S. Vitter. “Optimal External Memory Interval Management,” SIAM Journal on Computing, 32(6), 2003, 1488–1508. An extended abstract appears in “Optimal Dynamic Interval Management in External Memory,” Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science (FOCS ’96), Burlington, VT, October 1996, 560–569. Also appears in Abstracts of the 1st CGC Workshop on Computational Geometry, Center for Geometric Computing, Johns Hopkins University, Baltimore, MD, October 1996. http://dx.doi.org/10.1137/S009753970240481X
Items in KU ScholarWorks are protected by copyright, with all rights reserved, unless otherwise indicated.
We want to hear from you! Please share your stories about how Open Access to this item benefits YOU.