发明名称 |
基于MapReduce的大图上距离连接查询方法 |
摘要 |
本发明公开了一种基于MapReduce的大图上距离连接查询方法,其步骤包括:1)提取初始化的查询参数:原图、已访问结点、拓展范围和查询结果;2)在hadoop上对原图进行双向拓展,拓展从源结点集合和目标结点集合开始,每次拓展基于代价模型,采用动态阈值剪枝操作,将新拓展的结点加入已访问结点集合;3)继续遍历未完成拓展的剩余结点,直到所有满足拓展范围的结点都完成拓展;4)完成迭代后,记录所述已访问节点集合中目标结点和源结点间路径查询结果,返回查询结果。本发明在MapReduce环境下提出了一种基于代价模型的自适应方法,基于动态阈值进行剪枝的双向搜索算法和Segment索引减少拓展空间和迭代次数,提高任务的执行效率。 |
申请公布号 |
CN102737114A |
申请公布日期 |
2012.10.17 |
申请号 |
CN201210157463.X |
申请日期 |
2012.05.18 |
申请人 |
北京大学 |
发明人 |
周家帅;高军;王衎;王腾蛟;杨冬青;唐世渭 |
分类号 |
G06F17/30(2006.01)I |
主分类号 |
G06F17/30(2006.01)I |
代理机构 |
北京君尚知识产权代理事务所(普通合伙) 11200 |
代理人 |
余长江 |
主权项 |
基于MapReduce的大图上距离连接查询方法,其步骤包括:1)提取初始化的查询参数:原图、已访问结点、拓展范围和查询结果;2)在hadoop上对原图进行双向拓展,拓展从源结点集合和目标结点集合开始,每次拓展基于代价模型选择执行方式,采用动态阈值剪枝操作,将新拓展的结点加入已访问结点集合;3)继续遍历未完成拓展的剩余结点,直到所有满足拓展范围的结点都完成拓展;4)完成迭代后,记录所述已访问节点集合中目标结点和源结点间路径查询结果,返回查询结果。 |
地址 |
100871 北京市海淀区颐和园路5号 |