External Memory Range Reporting on a Grid | SpringerLink
Skip to main content
Springer Nature Link
Log in

External Memory Range Reporting on a Grid

  • Conference paper
Algorithms and Computation (ISAAC 2007)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 4835))

Included in the following conference series:

  • 1247 Accesses

Abstract

In this paper we present external memory data structures for orthogonal range reporting queries on a grid. Our data structure for two-dimensional orthogonal range reporting queries uses O((N/B)log2 N) blocks of space of size B and supports queries in optimal O(log2 log B U + T/B) time, where U is the size of universe, N is the number of elements in the data structure, and T is the size of the answer. Our data structure for three-sided range reporting queries that uses O(N/B) blocks of space and supports queries in O(log2 log B U + T/B) time. In the case of three-sided range reporting on a N×ℕ grid, we describe a \(O((N/B)\log^2_B N)\) space data structure with O(T/B) query time, a \(O((N/B)\log^*_B N)\) data structure with \(O(\log^*_B N +T/B)\) query time, and a O(N/B) space data structure with \(O(\log^{(k)}_B N +T/B)\) query time for any constant k.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Aggarwal, A., Vitter, J.S.: The Input/Output Complexity of Sorting and Related Problems. Communications of the ACM 31(9), 1116–1127 (1988)

    Article  MathSciNet  Google Scholar 

  2. Alstrup, S., Brodal, G.S., Rauhe, T.: New Data Structures for Orthogonal Range Searching. In: Proc. FOCS, pp. 198–207 (2000)

    Google Scholar 

  3. Amir, A., Efrat, A., Indyk, P., Samet, H.: Efficient Regular Data Structures and Algorithms for Dilation, Location, and Proximity Problems. Algorithmica 30(2), 164–187 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  4. Andersson, A.: Faster Deterministic Sorting and Searching in Linear Space. In: Proc. FOCS, pp. 135–141 (1996)

    Google Scholar 

  5. Arge, L.: External Memory Data Structures. In: Meyer auf der Heide, F. (ed.) ESA 2001. LNCS, vol. 2161, pp. 1–29. Springer, Heidelberg (2001)

    Chapter  Google Scholar 

  6. Arge, L., Samoladas, V., Vitter, J.S.: On Two-Dimensional Indexability and Optimal Range Search Indexing. In: Proc. PODS, pp. 346–357 (1999)

    Google Scholar 

  7. Beame, P., Fich, F.E.: Optimal Bounds for the Predecessor Problem and Related Problems. J. Comput. Syst. Sci. 65, 38–72 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  8. de Berg, M., van Kreveld, M.J., Snoeyink, J.: Two- and Three-Dimensional Point Location in Rectangular Subdivisions. J. Algorithms 18(2), 256–277 (1995)

    Article  MATH  MathSciNet  Google Scholar 

  9. Chan, T.M.: Point Location in o(log n) Time, Voronoi Diagrams in o(n log n) Time, and Other Transdichotomous Results in Computational Geometry. In: Proc. FOCS, pp. 333–344 (2006)

    Google Scholar 

  10. Chazelle, B.: A Functional Approach to Data Structures and its Use in Multidimensional Searching. SIAM J. on Computing 17, 427–462 (1988)

    Article  MATH  MathSciNet  Google Scholar 

  11. van Emde Boas, P., Kaas, R., Zijlstra, E.: Design and Implementation of an Efficient Priority Queue. Mathematical Systems Theory 10, 99–127 (1977)

    Article  MATH  Google Scholar 

  12. Fries, O., Mehlhorn, K., Näher, S., Tsakalidis, A.K.: A log log n Data Structure for Three-Sided Range Queries. Information Processing Letters 25(4), 269–273 (1987)

    Article  MATH  MathSciNet  Google Scholar 

  13. Grossi, R., Italiano, G.F.: Efficient Splitting and Merging Algorithms for Order Decomposable Problems. Information and Computation 154, 1–33 (1999)

    Article  MATH  MathSciNet  Google Scholar 

  14. Icking, C., Klein, R., Ottmann, T.: Priority Search Trees in Secondary Memory (Extended Abstract). In: Göttler, H., Schneider, H.-J. (eds.) WG 1987. LNCS, vol. 314, pp. 84–93. Springer, Heidelberg (1988)

    Google Scholar 

  15. Miltersen, P.B., Nisan, N., Safra, S., Wigderson, A.: On Data Structures and Asymmetric Communication Complexity. J. Comput. Syst. Sci. 57, 37–49 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  16. Nekrich, Y.: A Data Structure for Multi-Dimensional Range Reporting. In: Proc. SoCG 2007, pp. 344–353 (2007)

    Google Scholar 

  17. Overmars, M.H.: Efficient Data Structures for Range Searching on a Grid. J. Algorithms 9(2), 254–275 (1988)

    Article  MATH  MathSciNet  Google Scholar 

  18. Pǎtraşcu, M.: Planar Point Location in Sublogarithmic Time. In: Proc. FOCS, pp. 325–332 (2006)

    Google Scholar 

  19. Pǎtraşcu, M., Thorup, M.: Time-space Trade-offs for Predecessor Search. In: Proc. STOC, pp. 232–240 (2006)

    Google Scholar 

  20. Ramaswamy, S., Subramanian, S.: Path Caching: A Technique for Optimal External Searching. In: Proc. PODS, pp. 25–35 (1994)

    Google Scholar 

  21. Subramanian, S., Ramaswamy, S.: The P-range Tree: A New Data Structure for Range Searching in Secondary Memory. In: Proc. SODA, pp. 378–387 (1995)

    Google Scholar 

  22. Vitter, J.S.: External Memory Algorithms and Data Structures: Dealing with Massive Data. ACM Computing Surveys 33(2), 209–271 (2001)

    Article  Google Scholar 

  23. Willard, D.E.: New Trie Data Structures Which Support Very Fast Search Operations. Journal of Computer and System Sciences 28(3), 379–394 (1984)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Dept. of Computer Science, University of Bonn,  

    Yakov Nekrich

Authors
  1. Yakov Nekrich
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Takeshi Tokuyama

Rights and permissions

Reprints and permissions

Copyright information

© 2007 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Nekrich, Y. (2007). External Memory Range Reporting on a Grid. In: Tokuyama, T. (eds) Algorithms and Computation. ISAAC 2007. Lecture Notes in Computer Science, vol 4835. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-77120-3_46

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-77120-3_46

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-77118-0

  • Online ISBN: 978-3-540-77120-3

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation