Indexing the positions of continuously moving objects

By Simonas Šaltenis, Christian S. Jensen, Scott T. Leutenegger, M. Lopez. ACM SIGMOD Conference, 2000

1,032 citations recorded by the source corpus.

The coming years will witness dramatic advances in wireless communications as well as positioning technologies. As a result, tracking the changing positions of objects capable of continuous movement is becoming increasingly feasible and necessary. The present paper proposes a novel, R*-tree based indexing technique that supports the efficient querying of the current and projected future positions of such moving objects. The technique is capable of indexing objects moving in one-, two-, and three-dimensional space. Update algorithms enable the index to accommodate a dynamic data set, where objects may appear and disappear, and where changes occur in the anticipated positions of existing objects. A comprehensive performance study is reported.

Subfields: Artificial Intelligence, Information Systems, Signal Processing

View Paper: https://www.semanticscholar.org/paper/78b33011cc1068326b6be8ad84aabafdd81cdd6d

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 Information Systems

In Signal Processing

Citations in the corpus

SINA: scalable incremental processing of continuous queries in spatio-temporal databases (2004, result): “The TPR*-Tree: An Optimized Spatio-temporal Access Method for Predictive Queries.”
The TPR*-Tree: An Optimized Spatio-Temporal Access Method for Predictive Queries (2003, background): “These integrals are solved into closed formulae [SJLL00].”
Query and Update Efficient B + -Tree Based Indexing of Moving Objects (2010, background): “A detailed description of the R-tree [3] and the TPR-tree [2] can be found in the referenced papers.”
Novel Approaches to the Indexing of Moving Object Trajectories (2000, background): “In the literature, the following taxonomy exists: (a) work on indexing the present positions of objects and asking future queries (Kollios et al. 1999, Saltenis et al. 2000) and (b) work on indexing the past positions of objects and asking historical queries.”
A Survey on Trajectory Data Management, Analytics, and Learning (2020, background): “Note that the main difference between a moving object [135] and a trajectory is the distinction between a pointwise sequence and a continuous projection, and each of them often employs fundamentally different storage and algorithmic solutions.”
MV3R-Tree: A Spatio-Temporal Access Method for Timestamp and Interval Queries (2001, methodology): “TN00]. GSTD has been widely employed (e.g., [NST99, PJT00, SJ99 ]) as a benchmarking environment for”
Time-focused clustering of trajectories of moving objects (2006, methodology): “In this paper, we employ the model used in ( Saltenis, Jensen, Leutenegger & Lopez 2000 ), where the objects are assumed to move in a piecewise linear manner.”
Nearest neighbor and reverse nearest neighbor queries for moving objects (2002, methodology): “As the indexing structure for continuously moving points, the TPR-tree [18] has been used.”
External memory algorithms and data structures: dealing with massive data (2001, background): “[272] build the R-tree upon only the spatial dimensions, but parameterize the bounding box coordinates to account for the movement of the items stored within.”
Indexing spatio-temporal trajectories with Chebyshev polynomials (2004, background): “[44] consider indexing mobile objects and one-dimensional and two-dimensional space to answer range queries over the object locations into the future.”
Nearest Neighbor Search on Moving Object Trajectories (2005, methodology): “Using the TPR-tree (Time Parameterized Tree) structure [9], Benetis et al.”
Monitoring k-nearest neighbor queries over moving objects (2005, methodology): “Other existing methods that work in two or higher dimensional spaces utilize the TPR-tree (time-parameterized R-tree)[15] or its variants as the supporting index structure [1] [19] [13] [7].”
Indexing Large Trajectory Data Sets With SETI (2003, methodology): “The former class of queries can be answered by storing current position, speed and the direction of the moving objects [1, 14, 24, 25].”
Indexing Moving Points (2003, methodology): “[37] propose an indexing scheme based on R-trees for answering queries of type Q1 and Q2; its worst-case query time is also (n) I/Os.”