Chinese Journal of Computers   Full Text
Title	Hybrid Indexing of Moving Objects Based on Velocity Distribution
Authors	LIAO Wei TANG Gui-Fen JING Ning ZHONG Zhi-Nong
Address	(College of Electronic Science and Engineering， National University of Defense Technology， Changsha 410073)
Year	2007
Issue	No.4(661—671)
Abstract &   Background	Abstract TPR*-tree is the most popular indexing method for the current and future position of moving objects，but its frequent updates performance is very low. In this paper a hybrid indexing method, HVTPR-tree, which is based on the velocity distribution is presented for moving objects with frequent updates. HVTPR-tree takes into account the distribution of both velocity domain and space domain. First the velocity domain is split regularly, and moving objects are classified into different velocity buckets by their velocities, thus the moving objects in one bucket have similar velocities. Then TPR-tree is used to index the moving objects in each bucket. To support frequent updates a supplemented hash index on leaf nodes is added to HVTPR-tree. Also an extended bottom-up update algorithm is developed for HVTPR-tree, thus having a good dynamic update performance and concurrency. Experimental results show that HVTPR-tree’s update and query performance outperform any other indexing methods including TPR*-tree. keywords moving objects index; TPR*-tree; HVTPR-tree; extended bottom-up update algorithm background The work is supported by the National Natural Science Foundation of China under grant No.60472031 and the National High Technology Research and Development Program (863 Program) of China under grant No.2003AA5110. Moving objects indexing methods are becoming increasingly important due to numerous emerging applications such as traffic control, meteorology monitoring, and mobile computing. A hybrid indexing method, HVTPR-tree, which is based on the velocity distribution is presented for moving objects with frequent updates.