| Location based service (LBS) provides users with services related to their locations which can be obtained through mobile devices and wireless networks infrastructure. It has been widely used in both our daily lives and the military operations. Meanwhile, the coming era of 3G greatly accelerates the development of LBS. As people are most interested in query the massive information of the dynamic moving positions, thus the development of LBS promotes the study on the moving object database (MOD). Moving objects mean the object that can be located by some positioning devices. Cars that are equipped with GPS device, mobile phones that can be located by the mobile base station or the WiFi device are typical examples. As MOD technology has tremendous application potential and huge economy benefits in LBS, it has long been a research hotspot in the database field since 1997.After more than ten years' research, key technologies of MOD have been extensively studied and rich achievements have been got. However, MOD as a systematical application lacks the support of concurrent query processing. Especially, to improve the performance of concurrent query processing, there are urge requirements on studying the problems of memory index, concurrent control mechanism, concurrent continuous query, etc. Fortunately, the fast development of hardware technologies, taking chip multi-processors (CMP) and massive storage memory as the representatives provide significant opportunities and challenges. On one hand, the emerging massive storage memory means that we can index the frequently updated moving objects in memory to support highly efficient query processing. On the other hand, CMP has real parallel computing capability based on multi-threading, so that to develop multi-threaded algorithms on the multi-core architecture could improve query performance. Therefore, to study the concurrent query problem while considering the hardware technology has become a research trend.This dissertation applies the development of hardware technologies to the concurrent query processing of moving objects in LBS, and mainly studies two most important types of queries in concurrent query processing technologies: the concurrent predicted query and the concurrent continuous query. By designing and implementing a storage and query experimental system that supports multiple types of queries, the proposed algorithms are verified. Moreover, some typical application demonstrations of different types of queries are presented. The main works of this dissertation include:(1) The problem of concurrent predicted query is studied, and a moving object index that supports concurrent access is proposedThe predicted query of moving objects is always assisted by an efficient index. However, most of the existing indices for current and future locations of moving objects are based on disk storage, and the concurrent control mechanisms are seldom explored. Therefore, a memory index, i.e. the CS2B-tree that is cache sensitive is proposed, with its insert, delete and bulk loading algorithms. A concurrent control mechanism based on a two-level-lock protocol is designed to support concurrent access. Moreover, index update, predicted range query and predicted K nearest neighbor (KNN) query algorithms in the concurrent access context are proposed. The memory utilization of the index and the correctness of the concurrent control mechanism are analyzed theoretically. Experimental results show that: CS~2B-tree is suitable for memory implementation in real applications, and its query performance and concurrent access performance are both better than the traditional Bx-tree.(2) The multi-core and multi-threading technologies are considered when solving the problem of concurrent continuous query, and various novel query algorithms are proposedExisting concurrent continuous query algorithms use single thread to batch process the multiple concurrent queries, thus cannot fully utilize the parallel computing capability of the CMP. Therefore, the multi-core and multi-threading technologies are considered when designing the new algorithms. Firstly, focusing on the continuous query of moving objects in unconstraint space, a multi-threading based framework for continuous queries is proposed, which is composed of three sequential stages, i.e. the data updating stage, the sorting optimization stage and the query execution stage. Operations in each stage are multi-threaded. Focuses are put on the designing of various indices and query algorithms in the execution stage. The query index based range query algorithm and KNN algorithm, the object index based range query algorithm and KNN algorithm are proposed respectively. Secondly, focusing on the continuous query of moving objects in road networks, a multi-threading based framework for continuous queries is proposed, which is composed of two sequential stages, i.e. the data updating stage and the query execution stage. Similar to the former framework, these operations are also multi-threaded. Emphases are put on the designing of various query algorithms in the execution stage. The network expansion based range query algorithm as well as the Euclidean Restriction based range query algorithm and KNN algorithm are proposed respectively. Experimental results show that the multi-threading based framework is greatly helpful in improving query performance.(3) A storage and query experimental system that supports multiple types of queries is designed and implementedThe current implementations of MOD seldom support highly efficient concurrent query and lack typical demonstrations of query the dynamic moving objects in LBS. Therefore, a storage and query experimental system that supports multiple types of queries is designed and implemented. On one hand, it verifies the effectiveness and feasibleness of the proposed algorithms. On the other hand, it demonstrates the potential applications of different types of queries in LBS. In the implementation of the system, focuses are put on the two key technologies: the customized moving objects generator and the hybrid storage mechanism. The moving objects generator can approximately simulate objects moving on road networks, and quickly generate huge amount of objects, thus could satisfy the needs of simulating concurrent query processing. The hybrid storage mechanism uses the CS~2B-tree and the TB-tree to store the current and future positions and the historical positions separately in memory and disk, thus implements effective storage of moving objects and supports highly efficient execution of different types of queries. Meanwhile, the detailed functions and the related interfaces of the system are presented. Finally, the possible application demonstrations of the historical query, the continuous query and the predicted query are implemented respectively.
|
PDF Full Text Request