2000 | Simonas Šaltenis, Christian S. Jensen, Scott T. Leutenegger, Mario A. Lopez
This paper proposes a novel indexing technique, the time-parameterized R-tree (TPR-tree), for efficiently querying the current and projected future positions of moving objects. The TPR-tree extends the R*-tree and supports indexing of moving points in one-, two-, and three-dimensional space. It allows dynamic updates, accommodating objects that appear, disappear, or change positions. The technique stores functions of time that express the positions of moving objects, rather than static positions, enabling efficient querying without frequent updates.
The TPR-tree addresses two indexing problems: indexing current and future positions of moving objects, and indexing their trajectories. The former is focused on in this paper. The TPR-tree uses conservative bounding rectangles that are minimum at some time but may not be minimum at later times. These rectangles are time-parameterized, meaning their coordinates are functions of time, and they adapt to the movement of objects.
The TPR-tree supports three types of queries: timeslice, window, and moving. Timeslice queries retrieve points at a specific time, window queries retrieve points whose trajectories intersect a time interval, and moving queries retrieve points whose trajectories form a trapezoid. The TPR-tree efficiently handles these queries by using time-parameterized bounding rectangles and dynamic update algorithms.
The TPR-tree is compared with alternatives such as the R-tree and other indexing methods. It is shown to outperform these in terms of query performance, especially for skewed data. The TPR-tree's performance is also stable over time, unlike traditional multidimensional tree structures, which degrade as time progresses. The TPR-tree is scalable and can handle large numbers of objects, maintaining consistent performance as the data space scales.
The paper concludes that the TPR-tree is a promising solution for indexing moving objects, particularly in applications involving continuous movement and real-time tracking. Future work includes further optimization of the TPR-tree and exploration of its application in more complex scenarios.This paper proposes a novel indexing technique, the time-parameterized R-tree (TPR-tree), for efficiently querying the current and projected future positions of moving objects. The TPR-tree extends the R*-tree and supports indexing of moving points in one-, two-, and three-dimensional space. It allows dynamic updates, accommodating objects that appear, disappear, or change positions. The technique stores functions of time that express the positions of moving objects, rather than static positions, enabling efficient querying without frequent updates.
The TPR-tree addresses two indexing problems: indexing current and future positions of moving objects, and indexing their trajectories. The former is focused on in this paper. The TPR-tree uses conservative bounding rectangles that are minimum at some time but may not be minimum at later times. These rectangles are time-parameterized, meaning their coordinates are functions of time, and they adapt to the movement of objects.
The TPR-tree supports three types of queries: timeslice, window, and moving. Timeslice queries retrieve points at a specific time, window queries retrieve points whose trajectories intersect a time interval, and moving queries retrieve points whose trajectories form a trapezoid. The TPR-tree efficiently handles these queries by using time-parameterized bounding rectangles and dynamic update algorithms.
The TPR-tree is compared with alternatives such as the R-tree and other indexing methods. It is shown to outperform these in terms of query performance, especially for skewed data. The TPR-tree's performance is also stable over time, unlike traditional multidimensional tree structures, which degrade as time progresses. The TPR-tree is scalable and can handle large numbers of objects, maintaining consistent performance as the data space scales.
The paper concludes that the TPR-tree is a promising solution for indexing moving objects, particularly in applications involving continuous movement and real-time tracking. Future work includes further optimization of the TPR-tree and exploration of its application in more complex scenarios.