基于距离阈值的不确定图可达性查询处理

Distance Threshold-based Reachability Queries in Uncertain Graphs

在不确定数据的处理中,不确定图作为典型的数据模型得到了广泛的关注,研究的内容包括基于不确定图的子图匹配、最近邻查询及连接查询等,本文研究基于距离阈值的不确定图可达性查询,即给定不确定图及图中任意两点s、t和距离阈值d,返回s和t的d可达的概率.提出一种基于随机抽样的可达性查询处理算法.定义了一种不确定图可能图实例的分类树模型.为了提高图实例分类的获取效率,提出基于双向遍历的优化分类树模型.设计了基于图实例类抽样的可达性查询处理算法并通过理论分析和实验验证了算法的性能.

Uncertain graph receives widespread attention as a typical model in manipulating uncertain data,including subgraph matching queries,nearest neighbors queries,join queries and so on.This paper studys reachability queries.Given an uncertain graph G,two vertex s and t in G and distance threshold d,the query returns the probability that s and t is reachable within d.This paper proposes a sampling based reachability query processing algorithm.First,define a graph instance classification tree to partition the possible graph instances of an uncertain graph.In order to improve the efficiency on retrieving the graph instance classes,a bi-directional graph traversal based classification tree is designed.Finally,the threshold-based reachability query is processed by random sampling on the classification tree.The performance of the algorithm is evaluated through theoretical analysis and experimental verification.