.png){kind=icon}
返回
Efficient k-step Weighted Reachability Queries Processing Algorithms
.png){kind=icon}
PRE
AI
DOI：10.1007/s13369-025-10110-3.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
给定一个数据图G，一个源顶点u和可达性查询的目标顶点v，可达性查询用于回答在G中是否存在从u到v的路径。可达性查询处理是图数据管理中的基本操作之一，广泛应用于生物网络、通信网络和社会网络中，以辅助数据分析。实际应用中的数据图除了顶点之间的结构关系外，通常还包含与结构关系相关联的信息，如量化权重。因此，除了传统的可达性关系外，用户可能希望进一步了解这些可达性关系是否满足特定约束。本文研究了在加权图中高效处理k步加权可达性约束查询的问题。k步加权可达性查询用于回答在给定加权图中是否存在从源顶点u到目标顶点v的路径。如果存在，该路径需要满足：(1)路径中的所有边满足给定的权重约束，(2)路径长度不超过给定的距离阈值k。为解决该问题，首先提出了支持k步加权可达性查询处理和基于高效剪枝策略的索引构建方法的WKRI索引。其次，提出了基于部分顶点构建索引的思想，以减小索引大小，并基于顶点覆盖集设计了两种优化索引GWKRI和LWKRI。最后，在多个真实数据集上进行了实验。实验结果验证了本文提出的方法在回答k步加权可达性查询方面的效率。
Keyword:
Graph data management
Reachability query processing
k-step reachability queries
Weight-constrained reachability queries
期刊
IF:
5.7
论文数:
4.8K
被引数:
1.1W
机构
引用论文
.png){kind=icon}
分享收藏
查看更多内容