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

• 作者: 姜守旭 张海杰 邹兆年
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 不确定图 近邻查询 可靠期望距离 近邻关系图
• 年，卷（期）: 2011,（10）
• 所属期刊栏目: 数据库年会优秀论文
• 页码范围: 1885-1896
• 分类号: TP311
• 字数: 13539字
• 语种: 中文
• DOI: 10.3724/SP.J.1016.2011.01885

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	姜守旭	哈尔滨工业大学计算机科学与技术学院	47	622	12.0	24.0
2	邹兆年	哈尔滨工业大学计算机科学与技术学院	17	244	9.0	15.0
3	张海杰	哈尔滨工业大学计算机科学与技术学院	1	19	1.0	1.0