基于Map-Reduce的向量空间约束连接路径查询方法

作者：王俊陆; 张永普; 宋宝燕^*; 丁琳琳; 张师文

来源：小型微型计算机系统, 2018, 39(09): 2056-2059.

• 向量空间
• Map-Reduce
• 约束连接
• 路径查询

随着交通路网、社交网络等与空间位置有关的新型服务逐渐增多,向量空间数据规模正以极快速度增长和累积,传统数据处理技术在大规模向量空间数据上的执行效率及结果集优化等方面面临着巨大的挑战.本文提出一种基于Map-Reduce的向量空间约束连接路径查询算法,首先,算法在向量空间上进行等边距网格划分,以距离为阈值进行约束连接;其次,利用MapReduce框架,通过节点到单元格的筛选、节点所在约束区域的筛选、单向边集合的筛选以及节点到节点的距离筛选的四阶段筛选策略找到满足约束条件的全部备选路径,从而减少大量的文本复制和路径计算过程.实验表明,本文提出的算法具有较高的执行效率和较低的误差率.

• 单位
  辽宁大学