一种路网环境下的组k最近邻查询方法

摘要 针对已有的在路网中的组k最近邻（group k nearest neighbor，GkNN）查询方法存在的不足，提出了利用网格Voronoi图（Network Voronoi Diagram，NVD）的NVD-GkNN算法，具有较好的效果.该算法采用了三个步骤：处理数据集、过滤过程和精炼过程.处理数据集主要是计算查询点集Q的质心q.过滤过程主要是提前存储可能的查询结果.精炼过程主要是从可能的结果集合中找到查询结果.并且进一步给出了处理新增加点的ADDNVD-GkNN算法和处理删除点的DENVD-GkNN算法.实验表明所提算法在处理路网中的组k最近邻问题有明显的优势