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

Optimal Path Query Algorithm in Temporal Graphs

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

With the traffic，road networks，social networks and other space related new services gradually increased，the size of vector space data is growing and accumulating at a tremendous rate，traditional data processing technology is confronted with great challenges in the execution efficiency and optimization of result sets in large-scale vector space data.This paper presents a vector space constraint based on Map-Reduce connection path query algorithm.Firstly，algorithm from equilateral mesh in vector space，the distance threshold constraint connection；secondly，using the Map-Reduce framework，through the node to the cell selected node is selected，a one-way constraint edge set selected at the four stage and node distance selected delete node selection strategy to find the constraints of all alternative paths，thus reducing the amount of text and copy path calculation process.Experimental results show that the proposed algorithm has higher execution efficiency and lower error rate.