Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review
Final published version
Final published version
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 language | English |
---|---|
Title of host publication | 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016) |
Editors | Nicolas Ollinger, Heribert Vollmer |
Number of pages | 14 |
Volume | 47 |
Publisher | Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH |
Publication year | 2016 |
Pages | 23:1-23:14 |
Article number | 23 |
ISBN (print) | 978-3-95977-001-9 |
ISBN (Electronic) | 9783959770019 |
DOIs | |
Publication status | Published - 2016 |
Event | Symposium on Theoretical Aspects of Computer Science - Orléans, France Duration: 17 Feb 2016 → 20 Feb 2016 Conference number: 33 http://www.univ-orleans.fr/lifo/events/STACS2016/ |
Conference | Symposium on Theoretical Aspects of Computer Science |
---|---|
Nummer | 33 |
Land | France |
By | Orléans |
Periode | 17/02/2016 → 20/02/2016 |
Internetadresse |
Series | Leibniz International Proceedings in Informatics |
---|---|
ISSN | 1868-8969 |
See relations at Aarhus University Citationformats
ID: 108981313