Math @ Duke

Publications [#235422] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Arge, L; Erickson, J, Indexing moving points,
in Nineteenth Annual Symposium on Principles of Database Systems,
Proceedings of the ACM SIGACTSIGMODSIGART Symposium on Principles of Database Systems
(2000),
pp. 175186
(last updated on 2017/12/10)
Abstract: We propose three indexing schemes for storing a set S of N points in the plane, each moving along a linear trajectory, so that a query of the following form can be answered quickly: Given a rectangle R and a real value tq, report all K points of S that lie inside R at time tq. We first present an indexing structure that, for any given constant εGRT0, uses O(N/B) disk blocks, where B is the block size, and answers a query in O((N/B)1/2+ε+K/B) I/Os. It can also report all the points of S that lie inside R during a given time interval. A point can be inserted or deleted, or the trajectory of a point can be changed, in O(logB2 N) I/Os. Next, we present a general approach that improves the query time if the queries arrive in chronological order, by allowing the index to evolve over time. We obtain a tradeoff between the query time and the number of times the index needs to be updated as the points move. We also describe an indexing scheme in which the number of I/Os required to answer a query depends monotonically on the difference between tq and the current time. Finally, we develop an efficient indexing scheme to answer approximate nearestneighbor queries among moving points.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

