仲 悦，杜 明，周军锋

(东华大学，上海 201620)

0 引言

k步可达查询用于研究在给定的数据图上，起始点u是否能在路径长度不大于k的前提下到达目标顶点v。该研究有着广泛的用途[1-3]，例如在人际关系网络图[4]中，查询两个人能否通过 k个中间好友构成熟人关系；道路网络[5]中，用以查询用户是否可以从一个起点经过k条道路到达目的地等。

目前已有的 k步可达查询研究都是基于确定图[6-10]，然而不确定图[11]在实际生活中随处可见，此时两个实体之间的联系的强弱程度表现为边上的概率权值。例如，在道路网络中时常会出现拥堵的情况，而拥堵的严重程度可以用概率来刻画，从而导致本来可达的路径暂时性不可达；以及路由网络中，传感器测量误差导致两个路由之间的信号不稳定也会产生不确定的边。当给定一个不确定图，k步可达查询不但要求两点间可达，而且还要求出可达的概率。最朴素的方法是枚举所有的可能世界及其出现概率，接着计算每一个可能世界上u到v的可达情况，将结果相加。而每一个可能世界由于边的出现情况不同，无法用预先处理的索引对不同的可能世界进行查询。一个n条边的不确定图有2n个可能世界，呈指数级。因此，即使该方法能得到最精确的结果，当数据图达到比较大的规模后，这种枚举法显然无法进行，不具有扩展性。

针对上述问题，本文提出一种两阶段查询方法，用于加速不确定图上k步可达查询的处理。其基本思想是：对可达和不可达的查询基于不同索引分别处理。……