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

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_{B}log *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_{B}log *n* + *t*/*B*) I/Os
expected with high probability, and it can be updated in *O*(log_{B}log
*n*) I/Os amortized expected with high probability. The space remains
linear *O*(*n*/*B*).

arxiv-3sided.pdf (586 Kb)

**Links**

**BIBT _{E}X entry**

@techreport{arxiv-3sided, author = "Gerth St{\o}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" }