不确定图数据库中高效查询处理

• 作者: 张硕 李建中 邹兆年 高宏
• 来源期刊: 计算机学报
• 学科: 工学
• 关键词: 不确定性 不确定图 top-k查询 查询处理 图索引
• 年，卷（期）: 2009,（10）
• 页码范围: 2066-2079
• 页数: 14页
• 分类号: TP311
• 字数: 18158字
• 语种: 中文
• DOI: 10.3724/SP.J.1016.2009.02066

摘要

近年来,在多种领域中产生的大量数据都可以自然地建模为图结构,比如蛋白质交互网络、社会网络等.测量手段的不准确性以及数据本身的性质导致不确定性在很多图数据中普遍存在.文中研究不确定图数据库中的高效查询处理方法.首先给出一种数据模型来表示图的不确定性.鉴于对用户提交的查询图通常会产生大量匹配结果,高效得到概率最大的k个匹配常常更具有现实意义.因此文中形式化提出概率top-k子图匹配查询的问题.为了解决提出的查询问题,以附带概率信息的邻居子图为基础,设计了一种有效的索引结构.另外,提出一种高效的基于索引的查询处理方法.该查询处理方法的核心是一个基于搜索树的匹配算法,其中运用了一种概率剪枝技术来提高性能.实验结果表明,所提出方法具有良好的效率和可扩展性.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李建中	哈尔滨工业大学计算机科学与技术学院	237	6003	33.0	72.0
2	高宏	哈尔滨工业大学计算机科学与技术学院	109	1574	18.0	36.0
3	邹兆年	哈尔滨工业大学计算机科学与技术学院	17	244	9.0	15.0
4	张硕	哈尔滨工业大学计算机科学与技术学院	15	182	7.0	13.0