Simple and semi-dynamic structures for cache-oblivious planar orthogonal range searching

ABSTRACT

In this paper, we develop improved cache-oblivious data structures for two- and three-sided planar orthogonal range searching. Our main result is an optimal static structure for two-sided range searching that uses linear space and supports queries in O(log_BN + T/B) memory transfers, where B is the block size of any level in a multi-level memory hierarchy and T is the number of reported points. Our structure is the first linear-space cache-oblivious structure for a planar range searching problem with the optimal O(log_BN + T/B) query bound. The structure is very simple, and we believe it to be of practical interest.We also show that our two-sided range search structure can be constructed cache-obliviously in O(N log_BN) memory transfers. Using the logarithmic method and fractional cascading, this leads to a semi-dynamic linear-space structure that supports two-sided range queries in O(log₂ N + T/B) memory transfers and insertions in O(log₂N ⋅ log_B N) memory transfers amortized. This structure is the first (semi-)dynamic structure for any planar range searching problem with a query bound that is logarithmic in the number of elements in the structure and linear in the output size.Finally, using a simple standard construction, we also obtain a static O(N log₂ N)-space structure for three-sided range searching that supports queries in the optimal bound of O(log_B N + T/B) memory transfers. These bounds match the bounds of the best previously known structure for this problem; but our structure is much simpler, simple enough, we believe, to be of practical interest.

REFERENCES

• 1: Pankaj K. Agarwal , Lars Arge , Andrew Danner , Bryan Holland-Minkley, Cache-oblivious data structures for orthogonal range searching, Proceedings of the nineteenth annual symposium on Computational geometry, June 08-10, 2003, San Diego, California, USA [doi>10.1145/777792.777828]
• 2: 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, 1999.
• 3: 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]
• 4: Lars Arge, External memory data structures, Handbook of massive data sets, Kluwer Academic Publishers, Norwell, MA, 2002
• 5: 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]
• 6: Lars Arge , Gerth Stølting Brodal , Rolf Fagerberg , Morten Laustsen, Cache-oblivious planar orthogonal range searching and counting, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy [doi>10.1145/1064092.1064119]
• 7: Lars Arge , Mark de Berg , Herman Haverkort, Cache-oblivious R-trees, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy [doi>10.1145/1064092.1064120]
• 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 , Gerth Stlting Brodal , Rolf Fagerberg , Dongdong Ge , Simai He , Haodong Hu , John Iacono , Alejandro López-Ortiz, The Cost of Cache-Oblivious Searching, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.271, October 11-14, 2003
• 12: 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
• 13: 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
• 14: 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
• 15: J. L. Bentley. Decomposable searching problems. Information Processing Letters, 8(5):244--251, 1979.
• 16: G. S. Brodal. Personal communication, 2006.
• 17: 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
• 18: Gerth Stølting Brodal , Rolf Fagerberg, Funnel Heap - A Cache Oblivious Priority Queue, Proceedings of the 13th International Symposium on Algorithms and Computation, p.219-228, November 21-23, 2002
• 19: Gerth Stølting Brodal , Rolf Fagerberg, On the limits of cache-obliviousness, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780589]
• 20: 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
• 21: 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]
• 22: B. Chazelle and L. J. Guibas. Fractional cascading: I. A data structuring technique. Algorithmica, 1:133--162, 1986.
• 23: Douglas Comer, Ubiquitous B-Tree, ACM Computing Surveys (CSUR), v.11 n.2, p.121-137, June 1979 [doi>10.1145/356770.356776]
• 24: 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
• 25: Mark H. Overmars, Design of Dynamic Data Structures, Springer-Verlag New York, Inc., Secaucus, NJ, 1987
• 26: O. Procopiuc, P. K. Agarwal, L. Arge, and J. S. Vitter. Bkd-tree: A dynamic scalable kd-tree. In Proc. International Symposium on Spatial and Temporal Databases, LNCS 2750, pages 46--65, 2003.
• 27: H. Prokop. Cache-oblivious algorithms. Master's thesis, Massachusetts Institute of Technology, Cambridge, MA, June 1999.
• 28: 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
• 29: 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]
• 30: 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.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Algorithms, Design, Theory

Keywords:
cache-obliviousness, data structures, memory hierarchies, range searching