Font Size: a A A

Research And Implementation Of Optimized Moving K Nearest Neighbor Query Algorithms Based On Voronoi Diagram

Posted on:2014-07-07Degree:MasterType:Thesis
Country:ChinaCandidate:Y B BiFull Text:PDF
GTID:2308330473951166Subject:Computer system architecture
Abstract/Summary:PDF Full Text Request
In recent years, with the development of wireless communication and GPS(Global Positioning System) positioning technology, the research of query technology in mobile environment has become a hot topic in the field of mobile database. The k-nearest neighbor query over mobile objects is an important problem. Many works have been done on k-nearest neighbor query, such as Bx-tree, Bdual-tree, TPR-tree and so on. The more efficent one applies Voronoi diagram to k-nearest neighbor query, which utilizes the Voronoi diagram neighborhood characteristics and improves the efficicency of the query. However, the performance of the index is not very efficent when the ratio of the moving objects data size to the number of grid is low. Therefore, this thesis gives a further study on this issue.Firstly, the Del-VGQ index consists of Delaunay triangulation and Virtual Grid Quadtree (VGQ). It has same quick position locating capability as VGQ index and the characteristics of Delaunay triangulation which can express the adjacent objects, so it is suitable for moving query. However, when the Delaunay triangulation is built, it should guaranty the empty round rule. According to this rule, the system should recursively check around triangles when a Delaunay triangulation node is inserted or deleted, so it is time-consuming. The thesis utilizes the delayed removal strategy to optimize the Del-VGQ index, proposes a k-nearest neighbor query algorithm called OptDe1VGQKnnQuery and proves the correctness of the algorithm. The performance of the algorithm is evaluated in a simulated environment. The experimental results show that the new index has a good performance when the ratio of the data size to the number of grid is low.Secondly, quadtree is an import part of the Del-VGQ index, but it does not support nonuniform data. Through analysis of the situation, the thesis utilizes R-tree which supports uniform data, instead of quadtree, and proposes a algorithm called DelRtreeKnnQuery. The performance of the algorithm is evaluated in a simulated environment. The experimental results show that the new index has a good performance when the ratio of the data size to the number of the grid is low.Thirdly, the division of grid in the Del-VGQ index is fixed, which makes the number of moving objects within the grid have a huge difference and seriously affects the efficiency of the index when the distribution of the data is nonuniform. Through analysis of the situation, the thesis designs a uniform density model, in which the division of the grid is not fixed. In this model, the grid is divided only when the number of moving objects within the grid exceeds a certain threshold. It makes the number of moving objects within every grid equal as far as possible to improve the efficicency of the index. Then the thesis proposes a algorithm called De1VGQAVGKnnQuery and the performace of the alogrithm is evaluated in a simulated environment. The experimental results show that the new index has a good performance when the ratio of the data size to the number of the grid is low.
Keywords/Search Tags:moving objects index, k nearest neighbor query, Voronoi diagram
PDF Full Text Request
Related items