不确定图上的高效top-k近邻查询处理算法

摘要

图的不确定性普遍存在,研究不确定图的高效查询处理具有重要意义。文中提出了不确定图上一种新型查询——近邻查询。给定一个查询标签集R和距离约束σ,在不确定图G上进行近邻查询是要找到标签集包含R并且任意两个顶点间距离不超过σ的匹配顶点集。为解决该问题,文中首先提出了“可靠期望距离”,然后基于可靠期望距离建立了高效的近邻关系图索引,将不确定图上的近邻查询等价地转化为近邻关系图上的团查询问题,最后使用树搜索算法解决近邻关系图上的团查询问题。理论分析和实验结果表明文中提出的算法能够高效地完成不确定图上的top-k近邻查询。