(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202211304038.9 (22)申请日 2022.10.24 (71)申请人 杭州悦数 科技有限公司 地址 311100 浙江省杭州市余杭区仓前街 道时代未来之城5幢2 201室 (72)发明人 吴敏　黄凤仙　杨怡璇　梁振亚　 周瑶　岳通　古思为　褚俊鹏　 叶小萌　 (74)专利代理 机构 杭州创智卓英知识产权代理 事务所(普通 合伙) 33324 专利代理师 朱秀琴 (51)Int.Cl. G06F 16/51(2019.01) G06F 16/53(2019.01) G06F 16/27(2019.01) (54)发明名称 分布式图数据库中可达性索引的分层构建 方法和系统 (57)摘要 本申请涉及一种分布式图数据库中可达性 索引的分层构建方法和系统， 该方法基于图数据 的分区特性， 采用多种随机游走方式对跨分区和 分区内的图数据分别构建可达性索引， 形成双层 可达性索引， 并在构建双层可达性索引的过程 中， 随着图数据库中数据的持续更新， 控制可达 性索引也在线持续更新， 其中针对跨分区这种较 高成本的索引， 和分区内这种较低成本的索引， 采用不同的索引更新频率， 控制跨分区的索引的 变动频率低于分区内的索引的变动频率， 以减少 跨分区的网络通信开销， 通过本申请， 解决了相 关技术中缺乏适用于分布式图数据库的可达性 索引构建方法的问题。 权利要求书2页 说明书11页 附图3页 CN 115374299 A 2022.11.22 CN 115374299 A 1.一种分布式图数据库中可达性索引的分层构建方法， 其特 征在于， 所述方法包括： 在分布式图数据库内部， 基于 图数据的分区特性， 采用多种随机游走方式对跨分区和 分区内的图数据分别构建可达性索引， 形成双 层可达性索引； 其中， 在构建双层可达性索引的过程中， 随着图数据库中数据的持续更新， 控制跨分区 的索引的变动频率低于分区内的索引的变动频率。 2.根据权利要求1所述的方法， 其特 征在于， 构建双 层可达性索引过程包括： 在构建跨分区可达性索引时， 以第一候选集中的节点作为索引的链表的元素， 选择与 所述节点相邻且未游走 过的分区中的其 他节点加入所述链 表； 在构建分区内可达性索引时， 以第二候选集中的节点作为索引的链表的元素， 选择与 所述节点相邻且与所述节点处于相同分区内的节点加入所述链 表。 3.根据权利要求2所述的方法， 其特 征在于， 所述随机游走的方式包括： 在同一个分区内， 赋予当前节点的每个邻居节点相同的概率， 随机选择与所述节点相 邻的节点加入所述链表； 或者， 根据当前节点的邻居与当前节点上一步的来源节点的距离， 赋予每个邻居节点对应的概 率， 根据概 率选择与所述节点相邻的节点加入所述链 表。 4.根据权利要求3所述的方法， 其特 征在于， 所述随机游走的方式还 包括： 确定当前节点是否有邻居节点落在所述第一候选集或所述第二候选集中， 若是， 则选 择所述邻居节点加入所述链 表。 5.根据权利要求2所述的方法， 其特 征在于， 所述方法包括： 在所有分区均已被访 问的情况下， 或者， 在由跨分区链表组成的集合占用的内存达到 第一阈值的情况 下， 终止对跨分区可达性索引的更新； 在由分区内链表组成的集合占用的内存达到第 二阈值的情况下， 终止对本分区可达性 索引的更新。 6.根据权利要求2所述的方法， 其特 征在于， 所述方法还 包括： 在构建双层可达性索引的过程中， 针对第一候选集和第二候选集， 不断换出未被使用 的链表上 的点； 通过在同分区内或者跨分区进行多组随机游走， 确定序列中出现频率最高 的点或出入度较高的点并将其换入， 以降低假阴率。 7.根据权利要求2所述的方法， 其特 征在于， 所述方法包括： 在客户端对边发起删除操作的情况下， 删除边的两端的节点在分区内所有链表中的对 应节点及其邻边， 并删除边的两端的节点在跨分区链表中处于链表相 邻位置的对应节点及 其邻边； 响应于客户端的删除操作， 执 行图数据库的边删除操作的原有逻辑。 8.一种分布式图数据库中可达性索引的分层构建系统， 其特 征在于， 所述系统包括： 双层索引模块， 用于基于 图数据的分区特性， 采用多种随机游走方式对跨分区和分区 内的图数据分别构建可达性索引， 形成双 层可达性索引； 所述双层索引模块包括频率控制单元， 所述频率控制单元用于， 在构建双层可达性索 引的过程中， 随着图数据库中数据的持续更新， 控制跨分区的索引的变动频率低于分区内 的索引的变动频率。 9.一种电子装置， 包括存储器和处理器， 其特征在于， 所述存储器中存储有计算机程 序， 所述处理器被设置为运行所述计算机程序以执行权利要求1至7中任一项 所述的分布式权　利　要　求　书 1/2 页 2 CN 115374299 A 2图数据库中可达性索引的分层构建方法。 10.一种存储介质， 其特征在于， 所述存储介质中存储有计算机程序， 其中， 所述计算机 程序被设置为运行时执行权利要求1至7中任一项所述的分布式图数据库中可达性索引的 分层构建方法。权　利　要　求　书 2/2 页 3 CN 115374299 A 3