ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2015, Vol. 52 ›› Issue (3): 749-759.doi: 10.7544/issn1000-1239.2015.20131390

• 软件技术 • 上一篇    下一篇

动态数据集环境下的强邻近对查询

李松1,张丽平1,郝忠孝1,2   

  1. 1(哈尔滨理工大学计算机科学与技术学院 哈尔滨 150080); 2(哈尔滨工业大学计算机科学与技术学院 哈尔滨 150001) (lisongbeifen@163.com)
  • 出版日期: 2015-03-01
  • 基金资助: 
    基金项目:国家自然科学基金项目(61370084);黑龙江省自然科学基金项目(F201302);黑龙江省教育厅科学技术研究项目(12531z004,12541128)

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

摘要: 数据集中的强邻近对查询在空间数据挖掘、大数据处理、空间数据库、地理信息系统、数据的相似分析和推理等方面具有重要的作用. 已有的数据查询方法无法有效处理动态数据集中的强邻近对查询问题,针对动态数据集中的强邻近对查询的特点和复杂性,基于Voronoi图和R树空间索引结构提出了处理初始数据环境下的双数据集中的强邻近对查询算法VR_SNP. 针对分布区域不规则且数据点分布密度差异较大的情况利用Voronoi图进行计算查询,反之,则利用R树进行查询. 通过对初始强邻近对集和候选邻近对集进行二次判断计算,筛选出有效结果,给出了数据集动态增加和动态减少环境下的强邻近对查询算法VR_SNP_DA和算法VR_SNP_DE.进一步提出了移动点位置变化情况下的强邻近对查询算法VR_SNP_DL.理论研究和实验比较表明在数据集的数据量、新增点集和删除点集的规模较大、移动点的位置变化次数较多等情况下,所提出的算法具有较为明显的查询优势.

关键词: 空间数据库, 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)

中图分类号: