%0 Journal Article
%T All Pairs Label-constraint Path Query in Large Graph<br>大规模图上标签集约束路径的集合查询
%A BAO Jia-jia
%A TIAN Wei
%A <br>包佳佳
%A 田伟
%J 计算机科学
%D 2013
%I 
%X 图数据模型被广泛用于社交网络、生物技术、语义网络等开放、异构环境下的数据建模。标签集约束路径查询是基本路径查询问题之一,因其具有路径描述的灵活性而受到目前研究的重视。目前重点研究布尔查询问题:判断给定顶点对间是否有满足标签集约束的路径,返回是或否。 现研究布尔查询问题的正交问题,称为集合查询问题:给定标签约束集,返回满足标签集约束可达的顶点对。集合查询问题面临两个困难:1)简单地将集合查询问题简化为布尔查询问题的迭代会陷入穷举困境；2)压缩传递闭包的生成树结构虽然能够有效地回答布尔查询问题,但是,这种压缩结构不能有效支持集合查询,因为集合查询需要搜索满足约束连通的所有顶点对。为此,继续采用生成树来压缩标签路径传递闭包,用倒排索引表来加快集合查询所导致的搜索,并进一步给出两个优化算法。在大规模的数据集上的测试表明,本方法在时间和空间效率方面都具有优势。
%K Graph
%K Label-constraint path query
%K All pairs label-constraint path query
%K Inverted index<br>图
%K 标签集约束路径查询
%K 标签集约束路径的集合查询
%K 倒排索引
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=64A12D73428C8B8DBFB978D04DFEB3C1&aid=E61EC7D94804D7592EB57DBDB8AE3038&yid=FF7AA908D58E97FA&vid=1371F55DA51B6E64&iid=E158A972A605785F&sid=9D453329DCCABB94&eid=5BC9492E1D772407&journal_id=1002-137X&journal_name=计算机科学&referenced_num=0&reference_num=15