Efficient 3-D Range Searching in External Memory

D. E. Vengroff, and J. S. Vitter. ``Efficient 3-D Range Searching in External Memory,'' Proceedings of the 28th Annual ACM Symposium on Theory of Computing (STOC '96), Philadelphia, PA, May 1996.

Full text (gzip-compressed postscript)

Full text (Adobe pdf format)

We present a new approach to designing data structures for the important problem of external-memory range searching in two and three dimensions. We construct data structures for answering range queries in $O((\log \log \log_B N)\log_B N + {K}/{B})$ I/O operations, where N is the number of points in the data structure, B is the I/O block size, and K is the number of points in the answer to the query. We base our data structures on the novel concept of B-approximate boundaries, which are manifolds that partition space into regions based on the output size of queries at points within the space.

Our data structures answer a longstanding open problem by providing three dimensional results comparable to those provided by Sairam and Ramaswamy for the two dimensional case, though completely new techniques are used. Ours is the first 3-D range search data structure that simultaneously achieves both a base-B logarithmic search overhead (namely, $(\log \log \log_B N)\log_B N$) and a fully blocked output component (namely, K/B). This gives us an overall I/O complexity extremely close to the well-known lower bound of $\Omega(\log_B N + {K}/{B})$. The space usage is more than linear by a logarithmic or polylogarithmic factor, depending on type of range search.