Boosting moving object indexing through velocity partitioning

Thi Nguyen, Zhen He, Rui Zhang, Phillip Ward

Research output: Contribution to journalArticleResearchpeer-review

23 Citations (Scopus)


There have been intense research interests in moving object indexing in the past decade. However, existing work did not exploit the important property of skewed velocity distributions. In many real world scenarios, objects travel predominantly along only a few directions. Examples include vehicles on road networks, flights, people walking on the streets, etc. The search space for a query is heavily dependent on the velocity distribution of the objects grouped in the nodes of an index tree. Motivated by this observation, we propose the velocity partitioning (VP) technique, which exploits the skew in velocity distribution to speed up query processing using moving object indexes. The VP technique first identifies the "dominant velocity axes (DVAs)" using a combination of principal components analysis (PCA) and k-means clustering. Then, a moving object index (e.g., a TPR-tree) is created based on each DVA, using the DVA as an axis of the underlying coordinate system. An object is maintained in the index whose DVA is closest to the object's current moving direction. Thus, all the objects in an index are moving in a near 1-dimensional space instead of a 2-dimensional space. As a result, the expansion of the search space with time is greatly reduced, from a quadratic function of the maximum speed (of the objects in the search range) to a near linear function of the maximum speed. The VP technique can be applied to a wide range of moving object index structures. We have implemented the VP technique on two representative ones, the TPR*-tree and the B x-tree. Extensive experiments validate that the VP technique consistently improves the performance of those index structures.

Original languageEnglish
Pages (from-to)860-871
Number of pages12
JournalProceedings of the VLDB Endowment
Issue number9
Publication statusPublished - May 2012
Externally publishedYes
EventInternational Conference on Very Large Databases 2012 - Instanbul, Turkey
Duration: 27 Aug 201231 Aug 2012
Conference number: 38th

Cite this