  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 Bx-tree. Extensive experiments
validate that the VP technique consistently improves the performance of those
index structures.
