Indexing And Query Processing On Moving Objects In Location-Based Services

Location-based services provide users with services related to their positions which can be obtained through mobile devices and wireless networks infrastructure.The location-based services combine techniques in IT areas such as satellite navigation,mobile communications,internet and databases,thus have been becoming a unique and promising domain.With the repaid development of global positioning system(GPS),wireless cellular network,the moving objects databases techniques towards location-based services cannot meet the needs of users and face many challenges.In dynamic environment,the moving objects databases manage the positions of moving objects such as vehicles,airplanes and fleets,and provide location-dependent queries. Currently the researches in moving objects databases are preliminary and far from maturation both in theory and practice.And there are many open problems to solve.The indexing methods for current and future positions of moving objects and query techniques in dynamic environment,which are challenging directions,have been focused on by many researchers.In order to study the difficult and hot issues in moving objects databases,this paper gives comprehensive discusses and analysis on former work in related areas.And towards the application needs of satellite reconnaissance,this paper studies the key techniques in moving objects databases including indexing methods on moving objects, techniques of continuous k nearest neighbors query and predicted range aggregate query, and apply our achievements to practical applications.The main work and innovations are detailed as follows:1.A hybrid indexing method,HTPR-tree,which is based on TPR-tree and supplemented by a hash index,is presented to improve the lower performance of TPR-tree with frequent updates.Motivate by the bottom-up strategy of R-tree,an extended bottom-up update algorithm is developed for HTPR-tree and its cost model is also given.2.Based on thorough analysis on the query performance degrade of TPR-tree,we present a hybrid velocity distribution based time-parameterized R-tree(HVTPR-tree),which takes into account the distribution of both velocity domain and space domain and thus have a good query performance.3.In order to process continuous k nearest neighbors query based on TPR-tree efficiently,we present a new spatio-temporal distance metrics minmaxdist(t) as a pruning upper bound.Also a query algorithm based on extended spatio-temporal metrics (STM-CNN),searching in best-first manner,is developed.STM-CNN algorithm visits TPR-tree nodes according to mindist(t) order,and pruning the nodes with minmaxdist(t) to improve the query performance.4.To evaluate large collection of concurrent continuous k nearest neighbors queries continuously,we propose a scalable processing of incremental continuous k-nearest neighbor(SI-CNN) framework by introducing searching region to filter the visiting TPR-tree nodes.SI-CNN framework exploits incremental results table to buffer candidate objects and flushes the objects into query results in bulk.We then present an incremental SI-CNN query update algorithm,which evaluates incrementally based on former query answers and supports insertion or deletion of both query collection and moving objects.5.To improve the query performance of accurate predictive range aggregate(PRA) queries,we present an efficient predicted aggregate time-parameterized R-tree(aTPR-tree), which is based on TPR-tree structure and added with aggregate information in intermediate nodes to reduce the disk accesses of PRA queries.The aTPR-tree is supplemented by a hash index on leaf nodes,and uses bottom-up delete algorithm,thus having a good update performance and concurrency.Also an Enhanced predictive range aggregate(EPRA) query algorithm which uses a more precise branch and bound searching strategy is developed for aTPR-tree,reducing the node accesses greatly.Based on the above achievements,we design a remote sensing satellite targets reconnaissance query engine prototype and a location-based services experimental system fbr city emergency linkage to validate the efficiency and practice of our presented techniques including moving objects indexing methods,continuous k nearest neighbor query and predicted range aggregate query.