Pankaj K. Agarwal
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 IRd 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(log2B N) memory transfers. We also develop a static structure for the two-dimensional case that answers queries in O(logB N+T/B) memory transfers using O(N log22 N) space. The analysis of the latter structure requires that B=22c for some non-negative integer constant c.
- P. K. Agarwal, L. Arge, O. Procopiuc, and J. S. Vitter. A framework for index bulk loading and dynamization. In Proc. Annual International Colloquium on Automata, Languages, and Programming, pages 115--127, 2001.]] Google Scholar
Digital Library
- P. K. Agarwal, L. Arge, O. Procopiuc, and J. S. Vitter. Bkd-tree: A dynamic scalable kd-tree. Manuscript, 2002.]]Google Scholar
- 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.]]Google Scholar
- A. Aggarwal and J. S. Vitter. The Input/Output complexity of sorting and related problems. Communications of the ACM, 31(9):1116--1127, 1988.]] Google ScholarDigital Library
- A. Andersson and M. Thorup. Tight(er) worst-case bounds on dynamic searching and priority queues. In Proc. ACM Symp. on Theory of Computation, pages 335--342, 2000.]] Google ScholarDigital Library
- L. Arge. External memory data structures. In J. Abello, P. M. Pardalos, and M. G. C. Resende, editors, Handbook of Massive Data Sets, pages 313--358. Kluwer Academic Publishers, 2002.]] Google ScholarDigital Library
- L. Arge, M. Bender, E. Demaine, B. Holland-Minkley, and J. I. Munro. Cache-oblivious priority-queue and graph algorithms. In Proc. ACM Symp. on Theory of Computation, pages 268--276, 2002.]] Google ScholarDigital Library
- L. Arge, V. Samoladas, and J. S. Vitter. On two-dimensional indexability and optimal range search indexing. In Proc. ACM Symp. Principles of Database Systems, pages 346--357, 1999.]] Google ScholarDigital Library
- R. Bayer and E. McCreight. Organization and maintenance of large ordered indexes. Acta Informatica, 1:173--189, 1972.]]Google ScholarDigital Library
- M. Bender, R. Cole, E. Demaine, and M. Farach-Colton. Scanning and traversing: Maintaining data for traversals in memory hierarchy. In Proc. Annual European Symposium on Algorithms, pages 152--164, 2002.]] Google ScholarDigital Library
- M. A. Bender, R. Cole, and R. Raman. Exponential structures for cache-oblivious algorithms. In Proc. Annual International Colloquium on Automata, Languages, and Programming, pages 195--207, 2002.]] Google ScholarDigital Library
- M. A. Bender, E. D. Demaine, and M. Farach-Colton. Cache-oblivious B-trees. In Proc. IEEE Symp. on Foundations of Comp. Sci., pages 339--409, 2000.]] Google ScholarDigital Library
- M. A. Bender, Z. Duan, J. Iacono, and J. Wu. A locality-preserving cache-oblivious dynamic dictionary. In Proc. ACM-SIAM Symp. on Discrete Algorithms, pages 29--38, 2002.]] Google ScholarDigital Library
- J. L. Bentley. Multidimensional binary search trees used for associative searching. Communications of the ACM, 18:509--517, 1975.]] Google ScholarDigital Library
- J. L. Bentley. Decomposable searching problems. Information Processing Letters, 8(5):244--251, 1979.]]Google ScholarCross Ref
- G. S. Brodal and R. Fagerberg. Cache oblivious distribution sweeping. In Proc. Annual International Colloquium on Automata, Languages, and Programming, pages 426--438, 2002.]] Google ScholarDigital Library
- G. S. Brodal, R. Fagerberg, and R. Jacob. Cache oblivious search trees via binary trees of small height. In Proc. ACM-SIAM Symp. on Discrete Algorithms, pages 39--48, 2002.]] Google ScholarDigital Library
- B. Chazelle. Filtering search: a new approach to query-answering. SIAM J. Comput., 15(3):703--724, 1986.]] Google ScholarDigital Library
- B. Chazelle. A functional approach to data structures and its use in multidimensional searching. SIAM J. Comput., 17(3):427--462, June 1988.]] Google ScholarDigital Library
- B. Chazelle. Lower bounds for orthogonal range searching: I. the reporting case. Journal of the ACM, 37(2):200--212, Apr. 1990.]] Google ScholarDigital Library
- D. Comer. The ubiquitous B-tree. ACM Computing Surveys, 11(2):121--137, 1979.]] Google ScholarDigital Library
- M. Frigo, C. E. Leiserson, H. Prokop, and S. Ramachandran. Cache-oblivious algorithms. In Proc. IEEE Symp. on Foundations of Comp. Sci., pages 285--298, 1999.]] Google ScholarDigital Library
- H. Prokop. Cache-oblivious algorithms. Master's thesis, Massachusetts Institute of Technology, Cambridge, MA, June 1999.]]Google Scholar
- N. Rahman, R. Cole, and R. Raman. Optimized predecessor data structures for internal memory. In Proc. Workshop on Algorithm Engineering, LNCS 2141, pages 67--78, 2001.]] Google ScholarDigital Library
- J. Robinson. The K-D-B tree: A search structure for large multidimensional dynamic indexes. In Proc. SIGMOD Intl. Conf. on Management of Data, pages 10--18, 1981.]] Google ScholarDigital Library
- J. S. Vitter. External memory algorithms and data structures: Dealing with MASSIVE data. ACM Computing Surveys, 33(2):209--271, 2001.]] Google ScholarDigital Library
Index Terms
- Cache-oblivious data structures for orthogonal range searching
Recommendations
Cache-oblivious planar orthogonal range searching and counting
SCG '05: Proceedings of the twenty-first annual symposium on Computational geometryWe present the first cache-oblivious data structure for planar orthogonal range counting, and improve on previous results for cache-oblivious planar orthogonal range searching.Our range counting structure uses O(N log2 N) space and answers queries using ...
Orthogonal range searching on the RAM, revisited
SoCG '11: Proceedings of the twenty-seventh annual symposium on Computational geometryWe present a number of new results on one of the most extensively studied topics in computational geometry, orthogonal range searching. All our results are in the standard word RAM model: We present two data structures for 2-d orthogonal range ...
New data structures for orthogonal range searching
FOCS '00: Proceedings of the 41st Annual Symposium on Foundations of Computer ScienceWe present new general techniques for static orthogonal range searching problems in two and higher dimensions. For the general range reporting problem in R/sup 3/, we achieve query time O(log n+k) using space O(n log/sup 1+/spl epsiv// n), where n ...
Comments