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