公开(公告)号：CN102799624A

公开(公告)日：2012-11-28

申请号：CN201210210245.8

申请日：2012-06-19

Applicant: 北京大学

Inventor： 高军 ,  周家帅 ,  王腾蛟 ,  杨冬青 ,  唐世渭

IPC: G06F17/30

Abstract: 本发明涉及一种基于Datalog的分布式环境下大图数据查询方法，其步骤包括：1）对用户输入的基于Datalog规则集合的大图查询指令进行语法分析，产生对应的语法树；2）根据语法树，构建以Datalog规则为单位的执行计划。针对每个Datalog规则，构造对应的Map和Reduce执行函数。3）利用等价规则和统计数据，实现规则间优化、规则内优化、操作函数的优化，提高大图查询执行计划的效率。本发明为了简化最终用户编写图查询脚本的代价，提出了扩展的递归DataLog查询，支持用户使用简单的描述性语言来表达对应大图查询。本发明还提出了递归Datalog查询的MapReduce环境执行计划的构建方法，使得Datalog图查询能够在MapReduce框架下执行。

公开(公告)号：CN102722546A

公开(公告)日：2012-10-10

申请号：CN201210167376.2

申请日：2012-05-25

Applicant: 北京大学

Inventor： 周家帅 ,  高军 ,  蒋晓 ,  王腾蛟 ,  杨冬青 ,  唐世渭

IPC: G06F17/30

Abstract: 本发明提供一种在关系数据库环境下图中最短路径的查询方法，其步骤包括：将图存储于关系数据库中，按照该图中边的权重将该图对应的表划分成若干子表；根据查询请求中的源结点与目标结点建立已访问结点表，并初始化需要拓展的子表；采用宽度优先搜索方法对各个结点在选定的子表上进行迭代拓展；迭代拓展终止后，继续在原图的所有边上进行一次补充拓展，得到最短路径。本发明将一个大图划分成多个子图，分别存储在不同的数据库表中，使得查询拓展可以在较小的表上进行，能够获得更好的规模性和查询效率。

公开(公告)号：CN102629219A

公开(公告)日：2012-08-08

申请号：CN201210047028.1

申请日：2012-02-27

Applicant: 北京大学

Inventor： 王林青 ,  高军 ,  周家帅 ,  李红燕 ,  王腾蛟

IPC: G06F9/50

Abstract: 本发明涉及一种并行计算框架中的Reduce端自适应负载均衡方法，通过采用动态哈希函数划分方法来预测任务所输入数据的分布，并且根据所预测数据的分布特点产生一个静态哈希函数，使得在该静态哈希函数的作用下，所有数据的分发尽可能均匀地分配到各个计算节点中，进而任务调度能够根据数据分布的情况动态自适应地调整数据和计算资源的分配，减少了运算中出现的偏斜，提高了效率。

公开(公告)号：CN102629219B

公开(公告)日：2015-09-23

申请号：CN201210047028.1

申请日：2012-02-27

Applicant: 北京大学

Inventor： 王林青 ,  高军 ,  周家帅 ,  李红燕 ,  王腾蛟

IPC: G06F9/50

Abstract: 本发明涉及一种并行计算框架中的Reduce端自适应负载均衡方法，通过采用动态哈希函数划分方法来预测任务所输入数据的分布，并且根据所预测数据的分布特点产生一个静态哈希函数，使得在该静态哈希函数的作用下，所有数据的分发尽可能均匀地分配到各个计算节点中，进而任务调度能够根据数据分布的情况动态自适应地调整数据和计算资源的分配，减少了运算中出现的偏斜，提高了效率。

公开(公告)号：CN102737114A

公开(公告)日：2012-10-17

申请号：CN201210157463.X

申请日：2012-05-18

Applicant: 北京大学

Inventor： 周家帅 ,  高军 ,  王衎 ,  王腾蛟 ,  杨冬青 ,  唐世渭

IPC: G06F17/30

Abstract: 本发明公开了一种基于MapReduce的大图上距离连接查询方法，其步骤包括：1）提取初始化的查询参数:原图、已访问结点、拓展范围和查询结果；2）在hadoop上对原图进行双向拓展，拓展从源结点集合和目标结点集合开始，每次拓展基于代价模型，采用动态阈值剪枝操作，将新拓展的结点加入已访问结点集合；3）继续遍历未完成拓展的剩余结点，直到所有满足拓展范围的结点都完成拓展；4）完成迭代后，记录所述已访问节点集合中目标结点和源结点间路径查询结果，返回查询结果。本发明在MapReduce环境下提出了一种基于代价模型的自适应方法，基于动态阈值进行剪枝的双向搜索算法和Segment索引减少拓展空间和迭代次数，提高任务的执行效率。

公开(公告)号：CN102799624B

公开(公告)日：2015-03-04

申请号：CN201210210245.8

申请日：2012-06-19

Applicant: 北京大学

Inventor： 高军 ,  周家帅 ,  王腾蛟 ,  杨冬青 ,  唐世渭

IPC: G06F17/30

Abstract: 本发明涉及一种基于Datalog的分布式环境下大图数据查询方法，其步骤包括：1）对用户输入的基于Datalog规则集合的大图查询指令进行语法分析，产生对应的语法树；2）根据语法树，构建以Datalog规则为单位的执行计划。针对每个Datalog规则，构造对应的Map和Reduce执行函数。3）利用等价规则和统计数据，实现规则间优化、规则内优化、操作函数的优化，提高大图查询执行计划的效率。本发明为了简化最终用户编写图查询脚本的代价，提出了扩展的递归DataLog查询，支持用户使用简单的描述性语言来表达对应大图查询。本发明还提出了递归Datalog查询的MapReduce环境执行计划的构建方法，使得Datalog图查询能够在MapReduce框架下执行。

公开(公告)号：CN102737114B

公开(公告)日：2014-08-06

申请号：CN201210157463.X

申请日：2012-05-18

Applicant: 北京大学

Inventor： 周家帅 ,  高军 ,  王衎 ,  王腾蛟 ,  杨冬青 ,  唐世渭

IPC: G06F17/30

Abstract: 本发明公开了一种基于MapReduce的大图上距离连接查询方法，其步骤包括：1）提取初始化的查询参数:原图、已访问结点、拓展范围和查询结果；2）在hadoop上对原图进行双向拓展，拓展从源结点集合和目标结点集合开始，每次拓展基于代价模型，采用动态阈值剪枝操作，将新拓展的结点加入已访问结点集合；3）继续遍历未完成拓展的剩余结点，直到所有满足拓展范围的结点都完成拓展；4）完成迭代后，记录所述已访问节点集合中目标结点和源结点间路径查询结果，返回查询结果。本发明在MapReduce环境下提出了一种基于代价模型的自适应方法，基于动态阈值进行剪枝的双向搜索算法和Segment索引减少拓展空间和迭代次数，提高任务的执行效率。

公开(公告)号：CN102722546B

公开(公告)日：2015-07-29

申请号：CN201210167376.2

申请日：2012-05-25

Applicant: 北京大学

Inventor： 周家帅 ,  高军 ,  蒋晓 ,  王腾蛟 ,  杨冬青 ,  唐世渭

IPC: G06F17/30

Abstract: 本发明提供一种在关系数据库环境下图中最短路径的查询方法，其步骤包括：将图存储于关系数据库中，按照该图中边的权重将该图对应的表划分成若干子表；根据查询请求中的源结点与目标结点建立已访问结点表，并初始化需要拓展的子表；采用宽度优先搜索方法对各个结点在选定的子表上进行迭代拓展；迭代拓展终止后，继续在原图的所有边上进行一次补充拓展，得到最短路径。本发明将一个大图划分成多个子图，分别存储在不同的数据库表中，使得查询拓展可以在较小的表上进行，能够获得更好的规模性和查询效率。