10.3969/j.issn.1002-137X.2013.04.038
大规模图上标签集约束路径的集合查询
图数据模型被广泛用于社交网络、生物技术、语义网络等开放、异构环境下的数据建模.标签集约束路径查询是基本路径查询问题之一,因其具有路径描述的灵活性而受到目前研究的重视.目前重点研究布尔查询问题:判断给定顶点对间是否有满足标签集约束的路径,返回是或否.现研究布尔查询问题的正交问题,称为集合查询问题:给定标签约束集,返回满足标签集约束可达的顶点对.集合查询问题面临两个困难:1)简单地将集合查询问题简化为布尔查询问题的迭代会陷入穷举困境;2)压缩传递闭包的生成树结构虽然能够有效地回答布尔查询问题,但是,这种压缩结构不能有效支持集合查询,因为集合查询需要搜索满足约束连通的所有顶点对.为此,继续采用生成树来压缩标签路径传递闭包,用倒排索引表来加快集合查询所导致的搜索,并进一步给出两个优化算法.在大规模的数据集上的测试表明,本方法在时间和空间效率方面都具有优势.
图、标签集约束路径查询、标签集约束路径的集合查询、倒排索引
40
TP392(计算技术、计算机技术)
国家自然科学基金60973023,61003057
2013-06-27(万方平台首次上网日期,不代表论文的发表时间)
共6页
172-176,192