Font Size: a A A

The Research Of K-nearest Neighbor Query Of Spatial Data Based On Voronoi Diagram

Posted on:2017-08-03Degree:MasterType:Thesis
Country:ChinaCandidate:H D JingFull Text:PDF
GTID:2348330482984846Subject:Computer Science and Technology
Abstract/Summary:PDF Full Text Request
The technology of spatial data query plays an important role in spatial database, spatial data mining, spatial topological relationship analysis, intelligent transportation, geographic information system, and other fields. As a branch of spatial data query, nearest neighbor query plays an important role in realistic life.The nearest neighbor query can be divided into tow types: one is the query based on euclid space which can be divided into the query in obstructed spaces and the query without obstacle; Another one is the query in road network and in real life,most of the nearest neighbor query is in the condition of obstructed spaces or road network. The Voronoi diagram is a basic data structure with great potential to solve the problem of spatial query which is based on space partition. It can be applied to the geographic information system, online maps and other fields.Therefore, the emphasis of this paper is to utilize the Voronoi diagram to the nearest neighbor query and varieties in obstructed spaces and road network. The main research contents include:Firstly, based on the traditional k-nearest neighbor query in obstructed spaces,we analyze the shortage of traditional method and propose the k-nearest neighbor query method in obstructed spaces based on Voronoi diagram. At first we utilize the filtering function of Voronoi diagram to decrease the query data points. Then secondly filter the data points by obstructed distance and adjacent generation points. Finally we obtain the result by calculate in the candidate set.Secondly, according to the existing method of reverse nearest neighbor query in road network, we proposed the algorithm by using the grid Voronoi diagram which has great execution efficiency. The algorithm divide the road network into small grid Voronoi partition, then use the filtering function of grid Voronoi diagram to filter the data points that cannot be the result. Finally, we obtain the query result from the possible result set.The last,for the shortage of existing Group k-Nearest Neighbor query method in road network,the algorithm based on the Network Voronoi Diagram is proposed,that has better effect.This algorithm adopts three processes:processing data set,filtration process and refining process.Processing data set mainly calculate the centroid.The filtration process mainly store possible query results in advance. While the major task of refining process is to find query results from possible results sets.
Keywords/Search Tags:Voronoi diagram, k-nearest neighbor query, reverse nearest neighbor query, group k-nearest neighbor query
PDF Full Text Request
Related items