Aarhus University Seal

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

Research output: Contribution to book/anthology/report/proceedingArticle in proceedingsResearchpeer-review

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/B 1-ε logB N) IOs and queries in amortized O(1/ε log B N + K/B) IO s, 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-ε improvement over the previous best update bounds for these two query problems, while staying within the same query and space bounds.

Original languageEnglish
Title of host publication33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)
EditorsNicolas Ollinger, Heribert Vollmer
Number of pages14
PublisherSchloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH
Publication year2016
Article number23
ISBN (print)978-3-95977-001-9
ISBN (Electronic)9783959770019
Publication statusPublished - 2016
EventSymposium on Theoretical Aspects of Computer Science - Orléans, France
Duration: 17 Feb 201620 Feb 2016
Conference number: 33


ConferenceSymposium on Theoretical Aspects of Computer Science
SeriesLeibniz International Proceedings in Informatics

    Research areas

  • 3-sided range reporting, External memory, Priority search tree, Top-k queries

See relations at Aarhus University Citationformats

ID: 108981313