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

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