Research On Processing Of Nearest Neighbor And Reverse Nearest Neighbor Queries Over Moving Objects In Road Networks

With the rapid development of wireless technology and ever growing popularity of smart mobile devices, location-based services (LBSs) have become a reality. Being one of the enabling technologies, location-based queries (LBQs) have become a hot research topic. Recently, researchers have focused on LBQs, nearest neighbor (NN) queries and reverse nearest neighbor (RNN) queries in particular, and many research studies have been pro-posed. However, for NN query processing, there is no method which can handle continuous kNN queries over moving objects with uncertain speeds in road networks up to now. For RNN query processing, there is no method which can handle continuous RkNN queries over moving objects in road networks up to now. In particular, this method should handle continuous RkNN queries for both monochromatic data sets and bichromatic data sets. To the best of our knowledge, current location-based query methods are mainly based on point-to-point communication which is more suitable for light-loaded systems where contention for transmission channels and server resources is not severe, and they scale poorly when many users submit query requests to the server at the same time. Recently, researchers have begun to zero in on LBQs with periodic broadcast and some research results have appeared in the literature. To our knowledge, all the existing broadcast-based LBQ methods are lim-ited to Euclidean space, and none of them can be used in Network space. The previous LBQ methods proposed for use in Euclidean space can not give accurate query results, and hence it is essential to examine broadcast-based LBQ methods suitable for use in real road networks.This paper firstly discusses the issue of continuous reverse k nearest neighbor (CRkNN) queries over moving objects in road networks and analyzes the key technolo-gies about CRkNN query processing in road networks. A novel structure, which is called DLM tree, is proposed to represent the monitoring region of a CRkNN query. With the DLM tree, we can incrementally monitor the CRkNN query result, instead of computing it from the scratch whenever there is a location update. Several efficient algorithms have been proposed to support the processing of CRkNN queries on both monochromatic and bichromatic data sets. Several lemmas have been presented to prune the search space and some optimizing technologies have been presented to efficiently handle position updates of objects and queries. Experimental result shows that our approach is efficient and scalable.We address the problem of continuous k nearest neighbor (CkNN) queries over ob-jects moving with uncertain speeds (CUkNN) in road networks and discuss the limitations of previous CkNN query methods. A novel distance model has been presented to estimate the distances between objects and a submitted query, both of which move at uncertain speeds in the road network. Based on the proposed distance model, we present two CUkNN query monitoring methods, called CUkNNPLS and CUkNN Mean respectively, to continuously find the objects that could potentially be the k-nearest neighbors (kNN) of the query point during the time period being monitored. In CUkNNPLS method, by presenting the concepts Possible distance area and possible line segment(PLS), the probability calculation can be greatly simplified. In CUkNNMean, an efficient method is proposed to arrange all the potential objects in descending order of their probabilities of being a kNN of a query. Then the first k objects are chosen to form the final kNN result set. In addition, we address the issue of how to process object updates to maintain the query result. By organizing the data structures in a novel and neat way, we extend our method to handle CUkNN queries in large road networks with high efficiency and low disk access costs. Finally, the efficiency and scalability of the proposed methods are evaluated by extensive experiments.We research on the problem of continuous nearest neighbor queries in road networks under data broadcast environments (CNBNN). By marking each edge of the road network with the attribute obj_dom to indicate that the corresponding edge belongs to the Voronoi polygon of a certain object, a NVD structure is presented to preserve the properties of NVD. An efficient partition method, namely NVD quad partition, is proposed to partition the NVD structure into several grid cells from which we obtain a quad-tree, called NVD quad-tree, to keep the cells of the NVD structure. In particular, the grid cells of the NVD quad-tree we got are generally balanced in size and have good locality-preserving behavior. Then, a NVD-based distributed index, namely NVD-DI, is proposed to support NN/CNN query processing. NVD-DI index exhibits the following properties:1) it allows an NN/CNN search to start its execution at arbitrary time instants; 2) each search operation can be done within one broadcast cycle length; 3) it can significantly reduce energy consumption with acceptable access latency overhead. Finally, CNBNN query method is proposed. Extensive performance evaluation shows that the proposed CNBNN method performs significantly better than the D-tree based method.