Trajectory Indexing for Efficient Processing of Range Queries

The KIPS Transactions:PartD, Vol. 16, No. 4, pp. 487-496, Aug. 2009
10.3745/KIPSTD.2009.16.4.487,   PDF Download:


This paper addresses an indexing scheme capable of efficiently processing range queries in a large-scale trajectory database. After discussing the drawbacks of previous indexing schemes, we propose a new scheme that divides the temporal dimension into multiple time intervals and then, by this interval, builds an index for the line segments. Additionally, a supplementary index is built for the line segments within each time interval. This scheme can make a dramatic improvement in the performance of insert and search operations using a main memory index, particularly for the time interval consisting of the segments taken by those objects which are currently moving or have just completed their movements, as contrast to the previous schemes that store the index totally on the disk. Each time interval index is built as follows: First, the extent of the spatial dimension is divided onto multiple spatial cells to which the line segments are assigned evenly. We use a 2D-tree to maintain information on those cells. Then, for each cell, an additional 3D R*-tree is created on the spatio-temporal space (x, y, t). Such a multi-level indexing strategy can cure the shortcomings of the legacy schemes. Performance results obtained from intensive experiments show that our scheme enhances the performance of retrieve operations by 3~10 times, with much less storage space.

Show / Hide Statistics

Statistics (Cumulative Counts from September 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.

Cite this article
[IEEE Style]
C. I. Cha, S. W. Kim, J. I. Won, "Trajectory Indexing for Efficient Processing of Range Queries," The KIPS Transactions:PartD, vol. 16, no. 4, pp. 487-496, 2009. DOI: 10.3745/KIPSTD.2009.16.4.487.

[ACM Style]
Chang Il Cha, Sang Wook Kim, and Jung Im Won. 2009. Trajectory Indexing for Efficient Processing of Range Queries. The KIPS Transactions:PartD, 16, 4, (2009), 487-496. DOI: 10.3745/KIPSTD.2009.16.4.487.