Research On Two Layers Of Indexing Structures Of Moving Objects Based On Constrained Networks

In recent years, as an important branch of mobile computing technology and as one of the support technologies of location based services, moving object database has received widely attention and research. It accumulates a large amount of trajectory data relevant the positions of objects in moving objects databases. Due to the subjective and objective factors, the behavior of moving objects has the typical characteristic of dynamic, uncertain, and real time. In order to support efficient query for past and current position of uncertain moving objects, it urgently needs to propose effective and efficient indexing structures. Applying efficient indexing structure to moving objects provides much convenience to several fields, for example, Geographic information system, intelligent navigation, real-time tracking, location-awareness services. The existing algorithms focus on the efficiency of maintaining the index structure or focus on the efficiency of index-based query processing. The algorithm which consider the performance of index maintenance as well as query is rarely reported. In this study, NDTR-tree and FNR-tree which are two typical indexing structures are introduced and implemented, and their advantages and disadvantages are further analyzed.This thesis aims to do research on indexing algorithms for network-constraint moving objects, which can greatly improve the performance of index maintenance and range query. A new algorithm called HNTR-tree is proposed in this study, which uses R*-tree to manage the static road networks. Particularly, a new data structure integrates R-tree, and HashMap and double linked list is applied to manage dynamic trajectories. HNTR-tree can improve the efficiency of creating and maintaining indexes, as well as improve the trajectory query efficiency. The major contributions of this thesis are given as follows:(1) A new algorithm called HNTR-tree is proposed in this study, This thesis introduces the structure and indexing creating and maintenance algorithms of HNTR-tree in detail. In addition, the algorithms of trajectory deletion and range query of moving objects are detailed presented.(2) Most of previous research work uses Oldenbourg or San Jose map as road network datasets, where road networks are composed of edges instead of roads. In this study, the datasets are generated based on Vector map of the city of Chengdu, the datasets does not only consider the edge information, but also the road which is composed of multiple edges in the real-world situation. The experiments on real datasets based on the map of Chengdu are conducted, and the results show that HNTR-tree can reduce the time cost of index creation and maintenance by an average gap of78.4%compared with NDTR-tree, as well as reduce the time cost of trajectory query by an average gap of9.8%. Furthermore, by comparing with FNR-tree, HNTR-tree has a31.7%improvement in accuracy of range query with small windows.(3) Based on the proposed algorithm in this thesis, a system called PathFinder is developed. It consists of such modules including road network generation, trajectories generation, index creating and maintenance.