On Two-Dimensional Indexability and Optimal Range Search Indexing

L. Arge, V. Samoladas, and J. S. Vitter. ``Two-Dimensional Indexability and Optimal Range Search Indexing,'' Proceedings of the 18th Annual ACM Symposium on Principles of Database Systems (PODS '99), Philadelphia, PA, May-June 1999.

Full text (gzip-compressed postscript)

Full text (Adobe pdf format)

In this paper we settle several longstanding open problems in theory of indexability and external orthogonal range searching. In the first part of the paper, we apply the theory of indexability to the problem of two-dimensional range searching. We show that the special case of 3-sided querying can be solved with constant redundancy and access overhead. From this, we derive indexing schemes for general 4-sided range queries that exhibit an optimal tradeoff between redundancy and access overhead.

In the second part of the paper, we develop dynamic external memory data structures for the two query types. Our structure for 3-sided queries occupies O(N/B) disk blocks, and it supports insertions and deletions in $O(\log_B N)$ I/Os and queries in $O(\log_B N + T/B)$ I/Os, where B is the disk block size, N is the number of points, and T is the query output size. These bounds are optimal. Our structure for general (4-sided) range searching occupies $\smash{O\bigl( (N/B) (\log (N/B)) / \log \log_B N \bigr)}$ disk blocks and answers queries in $O(\log_B N + T/B)$ I/Os, which are optimal. It also supports updates in $\smash{O\bigl ( (\log_B N)(\log (N/B))/ \log \log_B N\bigr)}$ I/Os.