A general approach for cache-oblivious range reporting and approximate range counting

ABSTRACT

We present cache-oblivious solutions to two important variants of range searching: range reporting and approximate range counting. The main contribution of our paper is a general approach for constructing cache-oblivious data structures that provide relative (1+ε)-approximations for a general class of range counting queries. This class includes three-sided range counting, 3-d dominance counting, and 3-d halfspace range counting. Our technique allows us to obtain data structures that use linear space and answer queries in the optimal query bound of O(log_B(N/K)) block transfers in the worst case, where K is the number of points in the query range. Using the same technique, we also obtain the first approximate 3-d halfspace range counting and 3-d dominance counting data structures with a worst-case query time of O(log(N/K)) in internal memory.

An easy but important consequence of our main result is the existence of O(N log N)-space cache-oblivious data structures with an optimal query bound of O(log_BN + K/B) block transfers for the reporting versions of the above problems. Using standard reductions, these data structures allow us to obtain the first cache-oblivious data structures that use near-linear space and achieve the optimal query bound for circular range reporting and K-nearest neighbour searching in the plane, as well as for orthogonal range reporting in three dimensions.

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, On approximate range counting and depth, Proceedings of the twenty-third annual symposium on Computational geometry, June 06-08, 2007, Gyeongju, South Korea [doi>10.1145/1247069.1247129]
• 3: 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
• 4: Peyman Afshani , Chris Hamilton , Norbert Zeh, Cache-oblivious range reporting with optimal queries requires superlinear space, Proceedings of the 25th annual symposium on Computational geometry, June 08-10, 2009, Aarhus, Denmark [doi>10.1145/1542362.1542412]
• 5: 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]
• 6: 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]
• 7: Pankaj K. Agarwal , Alon Efrat , Micha Sharir, Vertical Decomposition of Shallow Levels in 3-Dimensional Arrangements and Its Applications, SIAM Journal on Computing, v.29 n.3, p.912-953, Dec. 1999 to Jan. 2000 [doi>10.1137/S0097539795295936]
• 8: 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]
• 9: 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]
• 10: 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]
• 11: 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]
• 12: 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]
• 13: 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]
• 14: Boris Aronov , Sariel Har-Peled, On approximating the depth and related problems, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 15: B. Aronov and S. Har-Peled. On approximating the depth and related problems, 2005. http://valis.cs.uiuc.edu/sariel/research/papers/04/depth/.
• 16: 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
• 17: Timothy M. Chan, Low-Dimensional Linear Programming with Violations, SIAM Journal on Computing, v.34 n.4, p.879-893, 2005 [doi>10.1137/S0097539703439404]
• 18: 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]
• 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: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 21: 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
• 22: Roberto Grossi , Giuseppe F. Italiano, Efficient cross-trees for external memory, External memory algorithms, American Mathematical Society, Boston, MA, 1999
• 23: 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]
• 24: S. Har-Peled and M. Sharir. Relative ε-approximations in geometry, 2006. http://valis.cs.uiuc.edu/sariel/research/papers/06/relative/.
• 25: 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
• 26: H. Kaplan, E. Ramos, and M. Sharir. The overlay of minimization diagrams in a randomized incremental construction. manuscript.
• 27: H. Kaplan, E. Ramos, and M. Sharir. Range minima queries with respect to a random permutation, and approximate range counting. To appear in Discrete and Computational Geometry.
• 28: Haim Kaplan , Micha Sharir, Randomized incremental constructions of three-dimensional convex hulls and planar voronoi diagrams, and approximate range counting, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.484-493, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109611]
• 29: D. Kirkpatrick. Optimal search in planar subdivisions. SJC, 12:28--35, 1983.
• 30: 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]
• 31: J. Matousek. Range searching with efficient hierarchical cuttings. Discrete and Computational Geometry, 10(2):157--182, 1993.
• 32: J. Matousek. Geometric set systems. European Congress of Mathematics, 2:1--27, 1998.
• 33: Jiří Matoušek, Reporting points in halfspaces, Computational Geometry: Theory and Applications, v.2 n.3, p.169-186, Nov. 1992 [doi>10.1016/0925-7721(92)90006-E]
• 34: E. M. McCreight. Priority search trees. SIAM Journal on Computing, 14(2):257--276, 1985.
• 35: Franco P. Preparata , Michael I. Shamos, Computational geometry: an introduction, Springer-Verlag New York, Inc., New York, NY, 1985
• 36: 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.
• 37: 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]
• 38: 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]
• 39: V. Vapnik and A. Chervonenkis. On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and Its Applications, 16:264--280, 1971.

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