Indexing Moving Points

By Pankaj Kumar Agarwal, L. Arge, Jeff Erickson. Journal of computer and system sciences (Print), 2003

313 citations recorded by the source corpus.

We propose three indexing schemes for storing a set S of N points in the plane, each moving along a linear trajectory, so that any query of the following form can be answered quickly: Given a rectangle R and a real value t, report all K points of S that lie inside R at time t. We first present an indexing structure that, for any given constant e > 0, uses O(N/B) disk blocks and answers a query in O(N/B1/2+e + K/B)I/Os, where B is the block size. 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(log2BN) 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 the query time stamp t and the current time. Finally, we develop an efficient indexing scheme to answer approximate nearest-neighbor queries among moving points.

Subfields: Artificial Intelligence, Computer Graphics and Computer-Aided Design, Signal Processing

View Paper: https://www.semanticscholar.org/paper/2c0b632ab1b47013a3e1990ebf9c42183339a243

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Graphics and Computer-Aided Design

In Signal Processing

Citations in the corpus

Query Indexing and Velocity Constrained Indexing: Scalable Techniques for Continuous Queries on Moving Objects (2002, background): “The problem of answering a range query for a collection of moving objects is addressed in [3] through the use of indexing schemes using external range trees.”
Never Walk Alone: Uncertainty for Anonymity in Moving Objects Databases (2008, background): “The work in [20] instead of using the same k for all messages, allows each message to specify an independent anonymity value and the maximum spatial and temporal tolerance resolutions it can tolerate based on its privacy requirements.”
External memory algorithms and data structures: dealing with massive data (2001, methodology): “Agarwal et al. [2001a] apply weightbalanced B-trees to convert partition trees such as kd-trees, BBD trees, and BAR trees, which were designed for internal memory, into efficient EM data structures.”
Indexing spatio-temporal trajectories with Chebyshev polynomials (2004, background): “where G[1] and G[2] are the low bounds, and G[3] and G[4] are the high bounds along the value and time axes.”
Indexing Large Trajectory Data Sets With SETI (2003, background): “The former class of queries can be answered by storing current position, speed and the direction of the moving objects [1, 14, 24, 25].”
Discovering similar multidimensional trajectories (2002, background): “Lately, there has been some work on indexing moving objects to answer spatial proximity queries (range and nearest neighbor queries) [26, 1, 34].”
Querying imprecise data in moving object environments (2003, background): “The problems of indexing and efficient access of spatiotemporal objects have been addressed in [2], [9], [6], [20], [22].”
The TPR*-Tree: An Optimized Spatio-Temporal Access Method for Predictive Queries (2003, background): “Agarwal et al. [AAE00] extend the solutions to two dimensions with the kinetic approach [BGH97].”