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

摘要：

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

关键词：广义可达性查询、Path-tree编码、RB+索引

所属期刊栏目：6

分类号：TP391(计算技术、计算机技术)

资助基金：The National Natural Science Foundation of China under Grant Nos.61070055,91024032,91124001,60833005;the National Science and Technology Major Special Project of China under Grant No.2010ZX01042-002-003;the Research Funds of Renmin University of China under Grant Nos.11XNL010,10XNI018

在线出版日期：2012-12-05（万方平台首次上网日期，不代表论文的发表时间）

页数：共9页

页码：577-585