Document Open Access Logo

External Memory Three-Sided Range Reporting and Top-k Queries with Sublogarithmic Updates

Author Gerth Stølting Brodal

PDF
Thumbnail PDF

File

LIPIcs.STACS.2016.23.pdf
  • Filesize: 0.69 MB
  • 14 pages

Document Identifiers

Author Details

Gerth Stølting Brodal

Cite As Get BibTex

Gerth Stølting Brodal. External Memory Three-Sided Range Reporting and Top-k Queries with Sublogarithmic Updates. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 23:1-23:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.STACS.2016.23

Abstract

An external memory data structure is presented for maintaining a dynamic set of N two-dimensional points under the insertion and deletion of points, and supporting unsorted 3-sided range reporting queries and top-k queries, where top-k queries report the k points with highest y-value within a given x-range. For any constant 0 < epsilon <= 1/2, a data structure is constructed that supports updates in amortized O(1/(epsilon * B^{1-epsilon}) * log_B(N)) IOs and queries in amortized O(1/epsilon * log_B(N+K/B)) IOs, where B is the external memory block size, and K is the size of the output to the query (for top-k queries K is the minimum of k and the number of points in the query interval). The data structure uses linear space. The update bound is a significant factor B^{1-epsilon} improvement over the previous best update bounds for these two query problems, while staying within the same query and space bounds.

Subject Classification

Keywords
  • External memory
  • priority search tree
  • 3-sided range reporting
  • top-k queries

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Peyman Afshani, Gerth Stølting Brodal, and Norbert Zeh. Ordered and unordered top-k range reporting in large data sets. In Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 390-400. SIAM, 2011. Google Scholar
  2. Alok Aggarwal and Jeffrey Scott Vitter. The input/output complexity of sorting and related problems. Communications of the ACM, 31(9):1116-1127, 1988. URL: http://dx.doi.org/10.1145/48529.48535.
  3. Lars Arge. The buffer tree: A technique for designing batched external data structures. Algorithmica, 37(1):1-24, 2003. URL: http://dx.doi.org/10.1007/s00453-003-1021-x.
  4. Lars Arge, Vasilis Samoladas, and Jeffrey Scott Vitter. On two-dimensional indexability and optimal range search indexing. In Proceedings of the Eighteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, PODS, pages 346-357. ACM, 1999. Google Scholar
  5. Rudolf Bayer and Edward M. McCreight. Organization and maintenance of large ordered indices. Acta Informatica, 1:173-189, 1972. URL: http://dx.doi.org/10.1007/BF00288683.
  6. Gabriele Blankenagel and Ralf Hartmut Güting. XP-trees - external priority search trees. Technical Report Informatik-Bericht Nr. 92, Fern Universität Hagen, 1990. Google Scholar
  7. Manuel Blum, Robert W. Floyd, Vaughan R. Pratt, Ronald L. Rivest, and Robert Endre Tarjan. Time bounds for selection. Journal of Computer and System Sciences, 7(4):448-461, 1973. Google Scholar
  8. Gerth Stølting Brodal and Rolf Fagerberg. Lower bounds for external memory dictionaries. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 546-554. ACM/SIAM, 2003. Google Scholar
  9. Gerth Stølting Brodal, Rolf Fagerberg, Mark Greve, and Alejandro López-Ortiz. Online sorted range reporting. In Proceedings of the 20th International Symposium Algorithms and Computation, ISAAC, volume 5878 of Lecture Notes in Computer Science, pages 173-182. Springer, 2009. Google Scholar
  10. Greg N. Frederickson. An optimal algorithm for selection in a min-heap. Information and Computation, 104(2):197-214, 1993. Google Scholar
  11. John Iacono and Mihai Pǎtraşcu. Using hashing to solve the dictionary problem. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 570-582. SIAM, 2012. Google Scholar
  12. Christian Icking, Rolf Klein, and Thomas Ottmann. Priority search trees in secondary memory (extended abstract). In Graph-Theoretic Concepts in Computer Science, International Workshop, WG, volume 314 of Lecture Notes in Computer Science, pages 84-93. Springer, 1987. Google Scholar
  13. Paris C. Kanellakis, Sridhar Ramaswamy, Darren Erik Vengroff, and Jeffrey Scott Vitter. Indexing for data models with constraints and classes. Journal of Computing and System Sciences, 52(3):589-612, 1996. Google Scholar
  14. Edward M. McCreight. Priority search trees. SIAM Journal on Computing, 14(2):257-276, 1985. URL: http://dx.doi.org/10.1137/0214021.
  15. Mark H. Overmars. The Design of Dynamic Data Structures, volume 156 of Lecture Notes in Computer Science. Springer, 1983. URL: http://dx.doi.org/10.1007/BFb0014927.
  16. Saladi Rahul, Prosenjit Gupta, Ravi Janardan, and K. S. Rajan. Efficient top-k queries for orthogonal ranges. In Proceedings 5th International Workshop on Algorithms and Computation, WALCOM, volume 6552 of Lecture Notes in Computer Science, pages 110-121. Springer, 2011. Google Scholar
  17. Saladi Rahul and Yufei Tao. On top-k range reporting in 2D space. In Proceedings of the 34th ACM Symposium on Principles of Database Systems, PODS, pages 265-275. ACM, 2015. URL: http://dx.doi.org/10.1145/2745754.2745777.
  18. Sridhar Ramaswamy and Sairam Subramanian. Path caching: A technique for optimal external searching. In Proceedings of the Thirteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, PODS, pages 25-35. ACM, 1994. Google Scholar
  19. Cheng Sheng and Yufei Tao. Dynamic top-k range reporting in external memory. In Proceedings of the 31st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS, pages 121-130. ACM, 2012. Google Scholar
  20. Sairam Subramanian and Sridhar Ramaswamy. The P-range tree: A new data structure for range searching in secondary memory. In Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 378-387. ACM/SIAM, 1995. Google Scholar
  21. Yufei Tao. A dynamic I/O-efficient structure for one-dimensional top-k range reporting. In Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS, pages 256-265. ACM, 2014. URL: http://dx.doi.org/10.1145/2594538.2594543.
  22. Robert Endre Tarjan. Amortized computational complexity. SIAM Journal on Algebraic Discrete Methods, 6(2):306-318, 1985. Google Scholar
  23. Elad Verbin and Qin Zhang. The limits of buffering: A tight lower bound for dynamic membership in the external memory model. SIAM Journal on Computing, 42(1):212-229, 2013. URL: http://dx.doi.org/10.1137/110842211.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact