公开(公告)号：CN110297950A

公开(公告)日：2019-10-01

申请号：CN201910567059.1

申请日：2019-06-27

Applicant: 浙江大学 ,  杭州海康威视数字技术股份有限公司

Inventor： 高云君 ,  张天明 ,  陈璐 ,  陈刚 ,  浦世亮

IPC: G06F16/901 ,  G06F16/903

Abstract: 本发明公开了一种基于Blogel的分布式图受限可达性查询处理方法。给定海量图数据，利用并行索引技术，本方法能够快速的返回受限可达性查询的结果。本发明基于Blogel分布式图处理框架，利用并行技术，提升DVL索引的构建效率；利用索引判定方法，提升受限可达性查询的效率。本发明先在局部子图中为每个顶点计算中介中心性，将具有最大中介中心性的前k个顶点选为标志点，再构建DVL索引，为每个顶点计算其到标志点的最短路径距离标签集合Dout和标志点到此顶点的最短路径距离标签集合Din。最后本发明在查询阶段提出分布式受限可达性查询算法，利用索引判定方法快速返回查询结果。本发明提出的分布式图受限可达性查询处理效率明显好于现有的方法，提供了最佳的性能。

公开(公告)号：CN110377795A

公开(公告)日：2019-10-25

申请号：CN201910566655.8

申请日：2019-06-27

Applicant: 浙江大学 ,  杭州海康威视数字技术股份有限公司

Inventor： 高云君 ,  张天明 ,  陈刚 ,  浦世亮

IPC: G06F16/901 ,  G06F16/903

Abstract: 本发明公开了一种基于Blogel的分布式时态图可达性查询处理方法。本发明提出了三种时态图可达性查询，一为普通时态图可达性查询；二为最短时间间隔查询；三为最早到达时间查询。本发明基于Blogel分布式计算框架，利用时态顶点标签索引TVL，有效组织时态图的时态信息和图拓扑结构；利用批量和并行技术，提升TVL索引的构建效率；利用索引判定方法和剪枝技术，缩小图搜索空间，提升查询效率。本发明先在TVL索引构建阶段为每个顶点计算其可达的规范顶点标签集合Lout和可达此顶点的规范顶点标签集合Lin。而后本发明在查询阶段利用剪枝技术有效地缩减查询搜索空间，依据索引判定方法快速返回查询结果。本发明极大地提高了可达性查询处理效率，提供了最佳的性能。