不确定图是描述现实世界中对象之间不确定和模糊关系的有效工具。不确定图上的k步可达查询用于计算两点之间k步可达的概率。现有不确定图上k步可达查询处理方法主要是从起始点出发进行抽样,统计其中的可达个数,求得估计值,但是该方法在查询处理时效率较低。针对该问题,本文提出了高效的索引来改进不确定图上k步可达查询处理的效率。本文研究内容如下:首先,提出一种专门处理不可能k步可达的剪枝策略。其基本思想是基于最小顶点覆盖集构建确定图上的k步可达索引,用于快速识别肯定k步不可达的查询。在求解最小顶点覆盖集时,按照度从大到小的顺序选择顶点,以此减小覆盖集的规模。基于顶点覆盖集构建索引时,根据拓扑层数自下而上处理顶点,加快索引的构建。和已有方法直接抽样计算不同,本文方法首先通过k步可达索引快速判断确定图上k步之内肯定不可达的查询,从而可以避免对这部分查询进行昂贵的抽样计算操作。只有确定是k步可达的查询,本文方法才进行后续的可达概率计算。在计算可达概率时,本文基于路径缩小抽取的可能世界规模,并使用位向量提前存储可能世界的策略,使查询能直接得出结果。其次,提出两种优化策略来加速k步可达查询的处理效率。在概率计算方面,提出双向遍历抽样,以减少传统单向抽样时顶点数量快速增多所导致的性能低效问题。其基本思想是从两个查询点同时向对方广度优先遍历,始终选择度小的顶点优先扩展。同时,在遍历的过程中对冗余顶点进行标记,使抽样时涉及到的图规模再次缩小。在不可达查询检测方面,使用正反拓扑号进一步加速过滤不可达顶点对。最后,基于多个真实数据集对本文所提算法的高效性进行了实验。实验结果从索引构建时间、索引大小以及查询效率三个方面进行了分析,验证了本文所提方法能够快速求解不确定图上的k步可达查询。