有向图上的广义可达性查询处理方法

• 作者: 孟小峰 富丽贞
• 来源期刊: 计算机科学与探索
• 学科: 工学
• 关键词: 广义可达性查询 Path-tree编码 RB+索引
• 年，卷（期）: 2012,（7）
• 所属期刊栏目: 学术研究
• 页码范围: 577-585
• 分类号: TP391
• 字数: 4828字
• 语种: 中文
• DOI: 10.3778/j.issn.1673-9418.2012.07.001

摘要

随着社会网络、生物信息学、本体等应用的迅速发展,如何在图上进行高效的信息检索成为一个亟待解决的问题.两点间可达性查询是一种常见的查询方式,目前针对此类查询已经提出了许多算法.但是在一些应用中,这种查询语义并不能满足用户需求.基于此,提出了两种广义可达性查询语义.研究了如何在大图上进行高效的广义可达性查询的问题,依据Path-tree编码的特性提出了一种新的二级索引机制——RB+索引.基于RB+索引,针对不同类型查询提出了两种高效的查询处理方法.该方法充分利用Path-tree编码的特性,有效地处理广义可达性查询.通过实验对提出的索引和查询算法进行了验证.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	孟小峰	中国人民大学信息学院	135	6213	41.0	77.0
2	富丽贞	中国人民大学信息学院	3	35	1.0	3.0