《计算机学报》文章摘要   全文下载
文章题目	不确定图上的高效top-k近邻查询处理算法
作者	张海杰 姜守旭 邹兆年
作者单位	(哈尔滨工业大学计算机科学与技术学院 哈尔滨 150001)
发表年份	2011
发表月份	10期(1885—1896)
文章摘要	摘要 图的不确定性普遍存在，研究不确定图的高效查询处理具有重要意义.文中提出了不确定图上一种新型查询——近邻查询.给定一个查询标签集R和距离约束σ，在不确定图G上进行近邻查询是要找到标签集包含R并且任意两个顶点间距离不超过σ的匹配顶点集.为解决该问题，文中首先提出了 “可靠期望距离”，然后基于可靠期望距离建立了高效的近邻关系图索引，将不确定图上的近邻查询等价地转化为近邻关系图上的团查询问题，最后使用树搜索算法解决近邻关系图上的团查询问题.理论分析和实验结果表明文中提出的算法能够高效地完成不确定图上的top-k近邻查询. 关键词 不确定图；近邻查询；可靠期望距离；近邻关系图 中图法分类号 TP311 DOI号: 10.3724/SP.J.1016.2011.01885