Optimal Dynamic Interval Management in External Memory

L. Arge and J. S. Vitter. ``Optimal Dynamic Interval Management in External Memory,'' SIAM Journal on Computing, 32(6), 2003. 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 appeared in Abstracts of the 1st CGC Workshop on Computational Geometry, Center for Geometric Computing, Johns Hopkins University, Baltimore, MD, October 1996.

Full text (Adobe pdf format)

We present a space- and I/O-optimal external-memory data structure for answering stabbing queries on a set of dynamically maintained intervals. Our data structure settles an open problem in databases and I/O algorithms by providing the first optimal external-memory solution to the dynamic interval management problem, which is a special case of 2-dimensional range searching and a central problem for object-oriented and temporal databases and for constraint logic programming. Our data structure simultaneously uses optimal linear space (that is, O(N/B) blocks of disk space) and achieves the optimal $O(\log_B N + T/B)$ I/O query bound and $O(\log_B N)$I/O update bound, where B is the I/O block size and T the number of elements in the answer to a query. Our structure is also the first optimal external data structure for a 2-dimensional range searching problem that has worst-case as opposed to amortized update bounds. Part of the data structure uses a novel balancing technique for efficient worst-case manipulation of balanced trees, which is of independent interest.