一种高效的不确定图上k步可达查询处理算法

摘要

目的给定一个不确定图,k步可达查询返回u到v在k步以内可达的概率。方法目前关于k步可达的索引方法都只适用于确定图,而不确定图上通常采用直接抽样求估计值。结果本文提出一种两阶段概率图上k步可达查询策略:首先基于顶点覆盖集构建确定图的k步索引,用于快速过滤肯定不可达的查询;其次针对不确定图,使用基于路径和提前抽样的方法来回答查询。结论实验结果验证了本文方法的高效性。