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

Gerth Stølting Brodal

In Proc. 33rd Annual Symposium on Theoretical Aspects of Computer Science, volume 47 of Leibniz International Proceedings in Informatics, 23:1-23:14 pages. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany, 2016.


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<ε≤ 1/2, a data structure is constructed that supports updates in amortized O(1/(ε B1-ε)logB N) IOs and queries in amortized O(1/(ε)logB 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 B1-ε improvement over the previous best update bounds for these two query problems, while staying within the same query and space bounds.

Copyright notice

Creative Commons License ND

Online version

stacs16.pdf (611 Kb)




stacs16.pdf (428 Kb), stacs16.pptx (166 Kb)

BIBTEX entry

  author = "Gerth St{\o}lting Brodal",
  booktitle = "Proc. 33rd Annual Symposium on Theoretical Aspects of Computer Science",
  doi = "10.4230/LIPIcs.STACS.2016.23",
  isbn = "978-3-95977-001-9",
  pages = "23:1-23:14",
  publisher = "Schloss Dagstuhl - Leibniz-Zentrum f\"ur Informatik, Dagstuhl Publishing, Germany",
  series = "Leibniz International Proceedings in Informatics",
  title = "External Memory Three-Sided Range Reporting and Top-$k$ Queries with Sublogarithmic Updates",
  volume = "47",
  year = "2016"

Other versions