Optimal external memory interval management

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 pro...

Full description

Saved in:
Bibliographic Details
Published in:SIAM journal on computing 2003-01, Vol.32 (6), p.1488-1508
Main Authors: ARGE, Lars, VITTER, Jeffrey Scott
Format: Article
Language:English
Subjects:
Alliances
Applied sciences
Computer science
Computer science
control theory
systems
Data processing. List processing. Character string processing
Exact sciences and technology
Information systems. Data bases
Logic programming
Memory organisation. Data processing
Queries
Software
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0097-5397
1095-7111
DOI:10.1137/S009753970240481X