Abstract:  With the rapid growth of biological networks, social networks, ontologies and so on, there is a big need to efficiently query on a large graph to find useful information. Reachability query between two definite vertices is one of the most common queries. Now, there are lots of approaches to deal with it. However, in some applications, this kind of queries can’t satisfy users’ demands. Therefore, this paper proposes two kinds of general reachability semantics. Firstly, it analyzes the problem to efficiently process general reachability queries, according to the characteristics of Path-tree labeling, proposes a novel 2-level indexing structure, namely RB+. Then, based on RB+, it proposes two kinds of efficient approaches for the two kinds of general reachability queries, which make full use of the characteristics of Path-tree labeling. The experimental results show the effectiveness and efficiency of the proposed approaches.

Key words: general reachability query, Path-tree encoding, RB+ indexing

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

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