Dynamic 3-sided Planar Range Queries with Expected Doubly Logarithmic Time

Gerth Stølting Brodal, Alexis C. Kaporis, Apostolos Papadopoulos, Spyros Sioutas, Konstantinos Tsakalidis, and Kostas Tsichlas

Technical Report, 1201.2702, arXiv.org, 29 pages, January 2012.

Abstract

This work studies the problem of 2-dimensional searching for the 3-sided range query of the form [a,b]x(-∞,c] in both main and external memory, by considering a variety of input distributions. We present three sets of solutions each of which examines the 3-sided problem in both RAM and I/O model respectively. The presented data structures are deterministic and the expectation is with respect to the input distribution:

(1) Under continuous μ-random distributions of the x and y coordinates, we present a dynamic linear main memory solution, which answers 3-sided queries in O(log n+t) worst case time and scales with O(loglog n) expected with high probability update time, where n is the current num ber of stored points and t is the size of the query output. We externalize this solution, gaining O(log_B n + t/B) worst case and O(log_B log n) amortized expected with high probability I/Os for query and update operations respectively, where B is the disk block size.

(2) Then, we assume that the inserted points have their x-coordinates drawn from a class of smooth distributions, whereas the y-coordinates are arbitrarily distributed. The points to be deleted are selected uniformly at random among the inserted points. In this case we present a dynamic linear main memory solution that supports queries in O(loglog n+t) expected time with high probability and updates in O(loglog n) expected amortized time, where n is the number of points stored and t is the size of the output of the query. We externalize this solution, gaining O(loglog_B n+t/B) expected I/Os with high probability for query operations and O(log_Blog n) expected amortized I/Os for update operations, where B is the disk block size. The space remains linear O(n/B).

(3) Finally, we assume that the x-coordinates are continuously drawn from a smooth distribution and the y-coordinates are continuously drawn from a more restricted class of realistic distributions. In this case and by combining the Modified Priority Search Tree with the Priority Search Tree, we present a dynamic linear main memory solution that supports queries in O(loglog n+t) expected time with high probability and updates in O(loglog n) expected time with high probability. We externalize this solution, obtaining a dynamic data structure that answers 3-sided queries in O(log_Blog n + t/B) I/Os expected with high probability, and it can be updated in O(log_Blog n) I/Os amortized expected with high probability. The space remains linear O(n/B).

Online version

arxiv-3sided.pdf (586 Kb)

Links

• arxiv.org/abs/1201.2702

BIBT_EX entry

@techreport{arxiv-3sided,
  author = "Gerth Stølting Brodal and Alexis C. Kaporis and Apostolos Papadopoulos and Spyros Sioutas and Konstantinos Tsakalidis and Kostas Tsichlas",
  institution = "arXiv.org",
  month = "January",
  number = "1201.2702",
  pages = "29",
  title = "Dynamic 3-sided Planar Range Queries with Expected Doubly Logarithmic Time",
  year = "2012"
}