Boosting moving object indexing through velocity partitioning

There have been intense research interests in moving object index-ing 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 di-rections. Examples include vehicles on road networks, flights, peo-ple walking on the streets, etc. The search space for a query is heav-ily dependent on the velocity distribution of the objects grouped in the nodes of an index tree. Motivated by this observation, we pro-pose 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 “dom-inant velocity axes (DVAs) ” using a combination of principal com-ponents 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 cur-rent 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 re-duced, from a quadratic function of the maximum speed (of the ob-jects 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 Bx-tree. Extensive experiments validate that the VP technique consistently improves the performance of those index structures. 1