Cache-oblivious range reporting with optimal queries requires superlinear space

ABSTRACT

We consider a number of range reporting problems in two and three dimensions and prove lower bounds on the amount of space required by any cache-oblivious data structure for these problems that achieves an optimal query bound of O(log_BN + K/B) block transfers in the worst case, where K is the size of the query output.

The problems we study are three-sided range reporting, 3-d dominance reporting, and 3-d halfspace range reporting. We prove that, in order to achieve the above query bound or even a bound of O((log_B N)^c (1 + K/B)), for any constant c > 0, the structure has to use Ohmega(N (log log N)^ε) space, where ε > 0 is a constant that depends on c and on the constant hidden in the big-Oh notation of the query bound.

Our result has a number of interesting consequences. The first one is a new type of separation between the I/O model and the cache-oblivious model, as I/O-efficient data structures with the optimal query bound and using linear or O(N log^AST N) space are known for the above problems. The second consequence is the non-existence of a linear-space cache-oblivious persistent B-tree with worst-case optimal 1-d range reporting queries.

REFERENCES

• 1: Peyman Afshani, On Dominance Reporting in 3D, Proceedings of the 16th annual European symposium on Algorithms, September 15-17, 2008, Karlsruhe, Germany [doi>10.1007/978-3-540-87744-8_4]
• 2: Peyman Afshani , Timothy M. Chan, Optimal halfspace range reporting in three dimensions, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.180-186, January 04-06, 2009, New York, New York
• 3: Peyman Afshani , Chris Hamilton , Norbert Zeh, A general approach for cache-oblivious range reporting and approximate range counting, Proceedings of the 25th annual symposium on Computational geometry, June 08-10, 2009, Aarhus, Denmark [doi>10.1145/1542362.1542413]
• 4: 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]
• 5: Pankaj K. Agarwal , Lars Arge , Jeff Erickson , Paulo G. Franciosa , Jeffrey Scott Vitter, Efficient searching with linear constraints, Journal of Computer and System Sciences, v.61 n.2, p.194-216, Oct. 2000 [doi>10.1006/jcss.2000.1709]
• 6: 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]
• 7: 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]
• 8: 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]
• 9: Lars Arge , Mark de Berg , Herman J. Haverkort , Ke Yi, The Priority R-tree: a practically efficient and worst-case optimal R-tree, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007608]
• 10: 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]
• 11: Lars Arge , Norbert Zeh, Simple and semi-dynamic structures for cache-oblivious planar orthogonal range searching, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA [doi>10.1145/1137856.1137883]
• 12: 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
• 13: 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]
• 14: Timothy M. Chan, Random Sampling, Halfspace Range Reporting, and Construction of (= k)-Levels in Three Dimensions, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.586, November 08-11, 1998
• 15: Timothy M. Chan, Random Sampling, Halfspace Range Reporting, and Construction of \lowercase$(\le k)$-Levels in Three Dimensions, SIAM Journal on Computing, v.30 n.2, p.561-575, 2000 [doi>10.1137/S0097539798349188]
• 16: 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
• 17: Roberto Grossi , Giuseppe F. Italiano, Efficient cross-trees for external memory, External memory algorithms, American Mathematical Society, Boston, MA, 1999
• 18: Roberto Grossi , Giuseppe F. Italiano, Efficient splitting and merging algorithms for order decomposable problems, Information and Computation, v.154 n.1, p.1-33, Oct. 10, 1999 [doi>10.1006/inco.1999.2811]
• 19: Kothuri Venkata Ravi Kanth , Ambuj K. Singh, Optimal Dynamic Range Searching in Non-replicating Index Structures, Proceedings of the 7th International Conference on Database Theory, p.257-276, January 10-12, 1999
• 20: Christos Makris , Athanasios Tsakalidis, Algorithms for three-dimensional dominance searching in linear space, Information Processing Letters, v.66 n.6, p.277-283, June 30, 1998 [doi>10.1016/S0020-0190(98)00075-1]
• 21: E. M. McCreight. Priority search trees. SIAM Journal on Computing, 14(2):257--76, 1985.
• 22: O. Procopiuc, P. K. Agarwal, L. Arge, and J. S. Vitter. Bkd-tree: A dynamic scalable kd-tree. In Proceedings of the 8th International Symposium on Advances in Spatial and Temporal Databases, volume 2750 of Lecture Notes in Computer Science, pages 46--65. Springer-Verlag, 2003.
• 23: Edgar A. Ramos, On range reporting, ray shooting and k-level construction, Proceedings of the fifteenth annual symposium on Computational geometry, p.390-399, June 13-16, 1999, Miami Beach, Florida, United States [doi>10.1145/304893.304993]
• 24: 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]
• 25: Darren Erik Vengroff , Jeffrey Scott Vitter, Efficient 3-D range searching in external memory, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.192-201, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237864]
• 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.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

General Terms:
Algorithms, Design, Theory

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