关键词: 图,标签集约束路径查询,标签集约束路径的集合查询,倒排索引

Abstract: Graph data has been used to model open and heterogeneous data such as social network,biological network and semantic Web．The edge-labeled graphs are drawing the attention of researchers for its scalability to describe the path reachability．Its fundamental problem is about returning true or false of the label-constraint path query．Based on this,we put forward all pairs label-constraint path query problem．There are two kinds of difficulty to solve this problem:1) It needs to enumerate all pairs of vertices exhaustively if taking the label-constraint path query to solve it；2) The spanning tree method can’t support the all pairs path query problem even though it can answer the path query efficiently．In this work,we compressed the label path transitive closure through spanning tree and quickened the query time by inverted index technique．We also gave two optimal algorithms for the query when searching answers on the spanning tree．The extensive experiments value the effectiveness and efficiency of our approach both on computing time and storage space.

Key words: Graph,Label-constraint path query,All pairs label-constraint path query,Inverted index