ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2015, Vol. 52 ›› Issue (3): 749-759.doi: 10.7544/issn1000-1239.2015.20131390

Previous Articles     Next Articles

Strong Neighborhood Pair Query in Dynamic Dataset

Li Song1, Zhang Liping1, Hao Zhongxiao1,2   

  1. 1(College of Computer Science and Technology, Harbin University of Science and Technology, Harbin 150080); 2(College of Computer Science and Technology, Harbin Institute of Technology,Harbin 150001)
  • Online:2015-03-01

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)

CLC Number: