摘要
图数据模型被广泛用于社交网络、生物技术、语义网络等开放、异构环境下的数据建模。标签集约束路径查询是基本路径查询问题之一,因其具有路径描述的灵活性而受到目前研究的重视。目前重点研究布尔查询问题:判断给定顶点对间是否有满足标签集约束的路径,返回是或否。现研究布尔查询问题的正交问题,称为集合查询问题:给定标签约束集,返回满足标签集约束可达的顶点对。集合查询问题面临两个困难:1)简单地将集合查询问题简化为布尔查询问题的迭代会陷入穷举困境;2)压缩传递闭包的生成树结构虽然能够有效地回答布尔查询问题,但是,这种压缩结构不能有效支持集合查询,因为集合查询需要搜索满足约束连通的所有顶点对。为此,继续采用生成树来压缩标签路径传递闭包,用倒排索引表来加快集合查询所导致的搜索,并进一步给出两个优化算法。在大规模的数据集上的测试表明,本方法在时间和空间效率方面都具有优势。
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 teachability. 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 prob- lem： 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 effi- ciently. 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.
出处
《计算机科学》
CSCD
北大核心
2013年第4期172-176,192,共6页
Computer Science
基金
国家自然科学基金(60973023
61003057)资助
