利索能及
我要发布
收藏
专利号: 2020111872911
申请人: 杭州海康威视数字技术股份有限公司
专利类型:发明专利
专利状态:已下证
更新日期:2025-08-05
缴费截止日期: 暂无
联系人

摘要:

权利要求书:

1.一种基于图式数据结构查询对象之间关系信息的方法,其特征在于,该方法包括:在用于管理图式数据结构的数据的图管理系统侧,其中,图式数据结构包括:用于表示以通信节点为对象的顶点、以及用于表示通信节点之间的关系信息的边,所述图式数据结构用于表征通信节点的关系网络的电信网络,所述对象包括通信节点标识信息,所述图管理系统包括:与终端进行通信的交互层、执行查询任务的图计算引擎、以及图数据库,交互层接收来自终端查询任务,该查询任务包括:两个顶点和两个顶点之间待查询的路径长度,获取图式数据结构中的第一顶点和第二顶点,并确定第一顶点和第二顶点之间待查询的路径长度;

图计算引擎根据待查询的路径长度中最长路径长度,确定第一距离和第二距离,其中,所述第一距离表示从第一顶点出发的遍历阶数,所述第二距离表示从第二顶点出发的遍历阶数;

根据待查询的每种路径长度的阶数,确定该种路径长度对应的第一目标阶数和第二目标阶数,其中,第一目标阶数表示待确定的中间点到第一顶点的路径长度,第二目标阶数表示待确定的中间点到第二顶点的路径长度;

从第一顶点出发,遍历第一距离内的每阶顶点,并且将每阶顶点记录在对应阶数的记录表中;

从第二顶点出发,遍历第二距离内的每阶顶点,将每阶顶点记录在对应阶数的记录表中,并且,对于每种路径长度,在确定该种路径长度的第二目标阶数对应的任一顶点存在于第一顶点的与该种路径长度的第一目标阶数对应的记录表时,将该顶点确定为该种路径长度的一个中间点;

对于每种路径长度的每个中间点,根据第一顶点的记录表和第二顶点的记录表,确定该种路径长度的包含该中间点的每条路径,得到两顶点之间的可达路径,所述可达路径表示对象之间关系信息。

2.如权利要求1所述的方法,其特征在于,所述根据待查询的路径长度中最长路径长度,确定第一距离和第二距离,包括:确定所述最长路径长度除以二的商,并将该商作为第一距离;

将最长路径长度与第一距离的差值作为第二距离。

3.如权利要求1所述的方法,其特征在于,所述从第一顶点出发,遍历第一距离内的每阶顶点,并且将每阶顶点记录在对应阶数的记录表中,包括:从第一顶点出发,遍历第一距离内的每阶顶点,并且将每阶顶点记录在对应阶数的布隆过滤器或者布谷鸟过滤器中;

所述从第二顶点出发,遍历第二距离内的每阶顶点,将每阶顶点记录在对应阶数的记录表中,包括:从第二顶点出发,遍历第二距离内的每阶顶点,并且将每阶顶点记录在对应阶数的布隆过滤器或者布谷鸟过滤器中。

4.如权利要求1所述的方法,其特征在于,进一步包括:获取对图中顶点的筛选条件;

所述从第一顶点出发,遍历第一距离内的每阶顶点,并且将每阶顶点记录在对应阶数的记录表中,包括:从第一顶点出发,遍历第一距离内的每阶顶点,并且将每阶顶点中满足所述筛选条件的顶点记录在对应阶数的记录表中;

所述从第二顶点出发,遍历第二距离内的每阶顶点,将每阶顶点记录在对应阶数的记录表中,包括:从第二顶点出发,遍历第二距离内的每阶顶点,并且将每阶顶点中满足所述筛选条件的顶点记录在记录表中。

5.如权利要求1所述的方法,其特征在于,所述对于每种路径长度的每个中间点,根据第一顶点的记录表和第二顶点的记录表,确定该种路径长度的包含该中间点的每条路径,包括:对于每种路径长度的每个中间点,基于第一顶点的记录表,确定该中间点到第一顶点的路径;

对于每种路径的每个中间点,基于第二顶点的记录表,确定该中间点到第二顶点的路径;

对于每种路径的每个中间点,根据该中间点到第一顶点的路径和到第二顶点的路径,确定第一顶点与第二顶点之间的该种路径长度的包含该中间点的每条路径。

6.一种基于图式数据结构查询对象之间关系信息的图管理系统,其特征在于,所述图管理系统包括:与终端进行通信的交互层、执行查询任务的图计算引擎、以及图数据库,所述交互层包括:接口单元,接收来自终端查询任务,该查询任务包括:两个顶点和两个顶点之间待查询的路径长度,获取图的第一顶点和第二顶点,并确定第一顶点和第二顶点之间待查询的路径长度;

所述图计算引擎包括:

管理单元,根据待查询的路径长度中最长路径长度,确定第一距离和第二距离,其中,所述第一距离表示从第一顶点出发的遍历阶数,所述第二距离表示从第二顶点出发的遍历阶数;根据待查询的每种路径长度的阶数,确定该种路径长度对应的第一目标阶数和第二目标阶数,其中,第一目标阶数表示待确定的中间点到第一顶点的路径长度,第二目标阶数表示待确定的中间点到第二顶点的路径长度;

查询单元,从第一顶点出发,遍历第一距离内的每阶顶点,并且将每阶顶点记录在对应阶数的记录表中;从第二顶点出发,遍历第二距离内的每阶顶点,将每阶顶点记录在对应阶数的记录表中,并且,对于每种路径长度,在确定该种路径长度的第二目标阶数对应的任一顶点存在于第一顶点的与该种路径长度的第一目标阶数对应的记录表时,将该顶点确定为该种路径长度的一个中间点;

路径确定单元,对于每种路径长度的每个中间点,根据第一顶点的记录表和第二顶点的记录表,确定该种路径长度的包含该中间点的每条路径,得到两顶点之间的可达路径,所述可达路径表示对象之间关系信息;

其中,

图式数据结构包括:用于表示以通信节点为对象的顶点、以及用于表示通信节点之间的关系信息的边,所述图式数据结构用于表征通信节点的关系网络的电信网络,所述对象包括标识信息。

7.如权利要求6所述的图管理系统,其特征在于,所述查询单元根据下述方式从第一顶点出发,遍历第一距离内的每阶顶点,并且将每阶顶点记录在对应阶数的记录表中:从第一顶点出发,遍历第一距离内的每阶顶点,并且将每阶顶点记录在对应阶数的布隆过滤器或者布谷鸟过滤器中;

所述查询单元根据下述方式从第二顶点出发,遍历第二距离内的每阶顶点,将每阶顶点记录在对应阶数的记录表中:从第二顶点出发,遍历第二距离内的每阶顶点,并且将每阶顶点记录在对应阶数的布隆过滤器或者布谷鸟过滤器中。

8.如权利要求6所述的图管理系统,其特征在于,所述接口单元进一步用于:获取对图中顶点的筛选条件;

所述查询单元根据下述方式从第一顶点出发,遍历第一距离内的每阶顶点,并且将每阶顶点记录在对应阶数的记录表中:从第一顶点出发,遍历第一距离内的每阶顶点,并且将每阶顶点中满足所述筛选条件的顶点记录在对应阶数的记录表中;

所述查询单元根据下述方式从第二顶点出发,遍历第二距离内的每阶顶点,将每阶顶点记录在对应阶数的记录表中:从第二顶点出发,遍历第二距离内的每阶顶点,并且将每阶顶点中满足所述筛选条件的顶点记录在记录表中。

9.一种计算设备,其特征在于,包括:

存储器;

处理器;

程序,存储在该存储器中并被配置为由所述处理器执行,所述程序包括用于执行权利要求1‑5中任一项所述的方法的指令。

10.一种存储介质,存储有程序,所述程序包括指令,其特征在于,所述指令当由计算设备执行时,使得所述计算设备执行如权利要求1‑5中任一项所述的方法。