关键词: 空间数据库, Voronoi图, 动态数据集, 最近邻查询, 强邻近对查询

Abstract: The strong neighborhood pair query(SNP query) has important significance in the spatial data mining, big data processing, spatial database, geographic information system, similarity analysis and reasoning of data, etc. To remedy the deficiency of the existing work, according to the characteristic and complexity of the strong neighborhood pair query in dynamic dataset, a strong neighborhood pair query algorithm (VR_SNP algorithm) in the double data sets is proposed based on the Voronoi diagram and R tree. According to the irregular regions and uneven density of the points, the Voronoi diagram is used to query the strong neighborhood pair, conversely, the R tree is used to query the pair. Based on the secondary calculation and filtration for the initial neighborhood pair set, the VR_SNP_DA algorithm and VR_SNP_DE algorithm are given respectively to deal with the strong neighborhood pair query as the data sets increase and decrease dynamically. Furthermore, the VR_SNP_DL algorithm to deal with the query about the moving objects is studied. The theoretical study and the experimental results show that the algorithms have great advantages when the scale of the datasets are large and the positions of the points usually change.

Key words: spatial database, Voronoi diagram, dynamic dataset, near neighbor query, strong neighborhood pair query (SNP query)