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

Optimal Path Query Algorithm in Temporal Graphs

作　　者：王俊陆[1] 张永普 宋宝燕[1] 丁琳琳[1] 张师文 WANG Jun-lu;ZHANG Yong-pu;SONG Bao-yan;DING Lin-lin;ZHANG Shi-wen(School of Information,Liaoning University,Shenyang 110036,China)

机构地区：[1]辽宁大学信息学院,沈阳110036

出　　处：《小型微型计算机系统》2018年第9期2056-2059,共4页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(61472169;61502215)资助;国家重点研发计划项目(2016YFC0801406)资助;辽宁省教育厅一般项目(L2015193)资助;辽宁省博士科研启动基金项目(201501127)资助

摘　　要：随着交通路网、社交网络等与空间位置有关的新型服务逐渐增多,向量空间数据规模正以极快速度增长和累积,传统数据处理技术在大规模向量空间数据上的执行效率及结果集优化等方面面临着巨大的挑战.本文提出一种基于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.

关 键 词：向量空间 MAP-REDUCE 约束连接 路径查询 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]