高级检索

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

    Strong Neighborhood Pair Query in Dynamic Dataset

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

       

      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.

       

    /

    返回文章
    返回