Cache-oblivious data structures for orthogonal range searching

ABSTRACT

We develop cache-oblivious data structures for orthogonal range searching, the problem of finding all T points in a set of N points in IR^d lying in a query hyper-rectangle. Cache-oblivious data structures are designed to be efficient in arbitrary memory hierarchies.We describe a dynamic linear-size data structure that answers d-dimensional queries in O((N/B)^1-1/d+T/B) memory transfers, where B is the block size of any two levels of a multilevel memory hierarchy. A point can be inserted into or deleted from this data structure in O(log²_B N) memory transfers. We also develop a static structure for the two-dimensional case that answers queries in O(log_B N+T/B) memory transfers using O(N log₂² N) space. The analysis of the latter structure requires that B=2^2c for some non-negative integer constant c.

REFERENCES

• 1: Pankaj K. Agarwal , Lars Arge , Octavian Procopiuc , Jeffrey Scott Vitter, A Framework for Index Bulk Loading and Dynamization, Proceedings of the 28th International Colloquium on Automata, Languages and Programming,, p.115-127, July 08-12, 2001
• 2: P. K. Agarwal, L. Arge, O. Procopiuc, and J. S. Vitter. Bkd-tree: A dynamic scalable kd-tree. Manuscript, 2002.
• 3: P. K. Agarwal and J. Erickson. Geometric range searching and its relatives. In B. Chazelle, J. E. Goodman, and R. Pollack, editors, Advances in Discrete and Computational Geometry, volume 223 of Contemporary Mathematics, pages 1--56. American Mathematical Society, Providence, RI, 1999.
• 4: Alok Aggarwal , Jeffrey,S. Vitter, The input/output complexity of sorting and related problems, Communications of the ACM, v.31 n.9, p.1116-1127, Sept. 1988 [doi>10.1145/48529.48535]
• 5: Arne A. Andersson , Mikkel Thorup, Tight(er) worst-case bounds on dynamic searching and priority queues, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.335-342, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335344]
• 6: Lars Arge, External memory data structures, Handbook of massive data sets, Kluwer Academic Publishers, Norwell, MA, 2002
• 7: Lars Arge , Michael A. Bender , Erik D. Demaine , Bryan Holland-Minkley , J. Ian Munro, Cache-oblivious priority queue and graph algorithm applications, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509950]
• 8: Lars Arge , Vasilis Samoladas , Jeffrey Scott Vitter, On two-dimensional indexability and optimal range search indexing, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.346-357, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.304010]
• 9: R. Bayer and E. McCreight. Organization and maintenance of large ordered indexes. Acta Informatica, 1:173--189, 1972.
• 10: Michael A. Bender , Richard Cole , Erik D. Demaine , Martin Farach-Colton, Scanning and Traversing: Maintaining Data for Traversals in a Memory Hierarchy, Proceedings of the 10th Annual European Symposium on Algorithms, p.139-151, September 17-21, 2002
• 11: Michael A. Bender , Richard Cole , Rajeev Raman, Exponential Structures for Efficient Cache-Oblivious Algorithms, Proceedings of the 29th International Colloquium on Automata, Languages and Programming, p.195-207, July 08-13, 2002
• 12: M. A. Bender , E. D. Demaine , M. Farach-Colton, Cache-oblivious B-trees, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.399, November 12-14, 2000
• 13: Michael A. Bender , Ziyang Duan , John Iacono , Jing Wu, A locality-preserving cache-oblivious dynamic dictionary, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.29-38, January 06-08, 2002, San Francisco, California
• 14: Jon Louis Bentley, Multidimensional binary search trees used for associative searching, Communications of the ACM, v.18 n.9, p.509-517, Sept. 1975 [doi>10.1145/361002.361007]
• 15: J. L. Bentley. Decomposable searching problems. Information Processing Letters, 8(5):244--251, 1979.
• 16: Gerth Stølting Brodal , Rolf Fagerberg, Cache Oblivious Distribution Sweeping, Proceedings of the 29th International Colloquium on Automata, Languages and Programming, p.426-438, July 08-13, 2002
• 17: Gerth Stølting Brodal , Rolf Fagerberg , Riko Jacob, Cache oblivious search trees via binary trees of small height, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.39-48, January 06-08, 2002, San Francisco, California
• 18: Bernard Chazelle, Filtering search: a new approach to query answering, SIAM Journal on Computing, v.15 n.3, p.703-724, August 1986 [doi>10.1137/0215051]
• 19: Bernard Chazelle, Functional approach to data structures and its use in multidimensional searching, SIAM Journal on Computing, v.17 n.3, p.427-462, June 1988 [doi>10.1137/0217026]
• 20: Bernard Chazelle, Lower bounds for orthogonal range searching: I. The reporting case, Journal of the ACM (JACM), v.37 n.2, p.200-212, April 1990 [doi>10.1145/77600.77614]
• 21: Douglas Comer, Ubiquitous B-Tree, ACM Computing Surveys (CSUR), v.11 n.2, p.121-137, June 1979 [doi>10.1145/356770.356776]
• 22: Matteo Frigo , Charles E. Leiserson , Harald Prokop , Sridhar Ramachandran, Cache-Oblivious Algorithms, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.285, October 17-18, 1999
• 23: H. Prokop. Cache-oblivious algorithms. Master's thesis, Massachusetts Institute of Technology, Cambridge, MA, June 1999.
• 24: Naila Rahman , Richard Cole , Rajeev Raman, Optimised Predecessor Data Structures for Internal Memory, Proceedings of the 5th International Workshop on Algorithm Engineering, p.67-78, August 28-31, 2001
• 25: John T. Robinson, The K-D-B-tree: a search structure for large multidimensional dynamic indexes, Proceedings of the 1981 ACM SIGMOD international conference on Management of data, April 29-May 01, 1981, Ann Arbor, Michigan [doi>10.1145/582318.582321]
• 26: Jeffrey Scott Vitter, External memory algorithms and data structures: dealing with massive data, ACM Computing Surveys (CSUR), v.33 n.2, p.209-271, June 2001 [doi>10.1145/384192.384193]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.0 General

General Terms:
Algorithms

Keywords:
cache-oblivious, orthogonal range searching