-
题名基于拓扑序列的DAG子图包含查询算法研究
被引量：1
- 1
-
-
作者
奚业雷
吕建华
张柏礼
-
机构
东南大学计算机科学与工程学院
-
出处
《计算机研究与发展》
EI
CSCD
北大核心
2011年第S3期343-349,共7页
-
基金
国家自然科学基金项目(61073059)
江苏省自然科学基金项目(BK2010409)
-
文摘
图模型具有强大的表达能力,被广泛用于各种应用领域的数据建模.如何在大规模图数据库中进行高效子图包含查询是当前的研究难点之一.由于子图同构是一个NP完全问题,在现有的子图包含查询算法中,基于图特征的索引技术被广泛用来提高查询处理性能,但是这些索引结构的维护代价较高.针对有向无环图提出了一种基于拓扑序列的子图包含查询算法,首先根据图中节点的偏序关系将有向图分层拓扑为一个序列,然后利用序列间的匹配关系过滤出候选结果集,最后通过子图同构检测验证得到最终结果集.相关性能测试表明,该算法无需构造复杂的索引结构,便于图数据库的动态维护,在有向无环图在线查询性能上表现出色.
-
关键词
子图包含查询
有向无环图
拓扑序列
子图同构
图索引
-
Keywords
subgraph containment query
DAG
topological sequence
subgraph isomorphism
graph indexing
-
分类号
TP3
[自动化与计算机技术—计算机科学与技术]
-
-
题名选择-验证-过滤:一种迭代的子图包含查询处理机制
- 2
-
-
作者
吕建华
张柏礼
姜杉
陆宁云
王菲菲
-
机构
东南大学计算机科学与工程学院
计算机网络和信息集成教育部重点实验室(东南大学)
南京航空航天大学自动化学院
-
出处
《计算机研究与发展》
EI
CSCD
北大核心
2012年第10期2221-2228,共8页
-
基金
国家自然科学基金项目(61073059
61034005)
江苏省自然科学基金项目(BK2010409)
-
文摘
近年来,图模型广泛应用于生物信息、计算化学、语义网等领域.目前,"过滤-验证"机制被广泛用于子图包含查询,即首先根据图数据的特征构造索引,然后根据索引产生候选集,最后对候选集中的每一个图进行子图同构验证.在这类算法中,"过滤"阶段是关注的重点,力争过滤掉更多的数据;而"验证"阶段则只是单纯地进行候选图子图同构检测,并没有进一步优化查询性能的可能.因此,提出了一种新的子图包含查询的迭代处理机制:"选择-验证-过滤",可利用从子图同构验证过程中得到的信息,结合数据库中图数据之间的相关关系,进行迭代查询处理.该机制首先选择数据库中的图与查询图进行同构验证,然后根据本次验证得到的信息,结合图数据之间的子图映射关系,进行迭代查询处理.一旦子图同构验证成功则可直接获得查询结果,而若验证不成功,则可以缩小下次迭代的查询搜索空间.为提高验证成功概率,提出了一种基于搜索空间预测的图选择策略.大量实验表明,该算法具有较"过滤-验证"机制更高的查询处理性能.
-
关键词
图数据
子图包含查询
选择-验证-过滤
迭代算法
搜索空间优化
-
Keywords
graph data
subgraph containment query
selection-verification-filtering
iterativealgorithm
search space optimization
-
分类号
TP391
[自动化与计算机技术—计算机应用技术]
-
