Aarhus University Seal

Lower Bounds for Sorted Geometric Queries in the I/O Model

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperConference articleResearchpeer-review

We study sorted geometric query problems, a class of problems that, to the best of our knowledge and despite their applications, have not received much attention so far. Two of the most prominent problems in this class are angular sorting queries and sorted K-nearest neighbour queries. The former asks us to preprocess an input point set S in the plane so that, given a query point q, the clockwise ordering of the points in S around q can be computed efficiently. In the latter problem, the output is the list of K points in S closest to q, sorted by increasing distance from q. The goal in both problems is to construct a small data structure that can answer queries efficiently. We study sorted geometric query problems in the I/O model and prove that, when limited to linear space, the naïve approach of sorting the elements in S in the desired output order from scratch is the best possible. This is highly relevant in an I/O context because storing a massive data set in a superlinear-space data structure is often infeasible. We also prove that answering queries using I/Os requires space, where N is the input size, B is the block size, and M is the size of the main memory. This bound is unlikely to be optimal and in fact we can show that, for a particular class of “persistence-based” data structures, the space lower bound can be improved to Ω(N2 / MO(1)). Both these lower bounds are a first step towards understanding the complexity of sorted geometric query problems. All our lower bounds assume indivisibility of records and hold as long as B = Ω(logM/BN).
Original languageEnglish
Book seriesLecture Notes in Computer Science
Pages (from-to)48-59
Number of pages12
Publication statusPublished - 2012
EventAnnual European Symposium Algorithms - Ljubljana, Slovenia
Duration: 10 Sept 201212 Dec 2012
Conference number: 20


ConferenceAnnual European Symposium Algorithms

Bibliographical note

Title of the vol.: Algorithms – ESA 2012 : 20th Annual European Symposium, Ljubljana, Slovenia, September 10-12, 2012. Proceedings / ed. by Leah Epstein, Paolo Ferragina.
ISBN: 978-3-642-33089-6, 978-3-642-33090-2

See relations at Aarhus University Citationformats

ID: 51948832