大规模图数据匹配技术综述

被引：36

作者：

于静 ^{[1
,2
]}

刘燕兵 ^{[1
,2
]}

张宇 ^{[1
,3
,2
]}

刘梦雅 ^{[1
,3
,2
]}

谭建龙 ^{[1
,2
]}

郭莉 ^{[1
,2
]}

机构：

[1] 中国科学院信息工程研究所

[2] 信息内容安全技术国家工程实验室(中国科学院信息工程研究所)

[3] 中国科学院大学

来源：

计算机研究与发展 | 2015年 / 52卷 / 02期

关键词：

图数据管理; 图模式匹配; 精确匹配; 子图同构; 索引技术; 图搜索;

D O I：

暂无

中图分类号：

TP391.41 [];

学科分类号：

080203 ;

摘要：

在大数据时代海量的多源异构数据间存在着紧密的关联性,图作为表示数据之间关系的基本结构在社交网络分析、社会安全分析、生物数据分析等领域有着广泛应用.在大规模图数据上进行高效地查询、匹配是大数据分析处理的基础问题.从应用角度对用于图查询的图数据匹配技术的研究进展进行综述,根据图数据的不同特征以及应用的不同需求对图匹配问题分类进行介绍.同时,将重点介绍精确图匹配,包括无索引的匹配和基于索引的匹配,以及相关的关键技术、主要算法、性能评价等进行了介绍、测试和分析.最后对图匹配技术的应用现状和面临的问题进行了总结,并对该技术的未来发展趋势进行了展望.

引用

页码：391 / 409

页数：19

共 10 条

[1] 基于图数据挖掘算法的犯罪规律研究及应用 [J].

唐德权 ;

张悦 ;

贺永恒 ;

肖自红 .

计算机技术与发展, 2011, 21 (11) :89-91+95

[2] 基于存储优化的多模式串匹配算法 [J].

刘燕兵 ;

刘萍 ;

谭建龙 ;

郭莉 .

计算机研究与发展, 2009, 46 (10) :1768-1776

[3] Incremental Graph Pattern Matching [J].

Fan, Wenfei ;

Wang, Xin ;

Wu, Yinghui .

ACM TRANSACTIONS ON DATABASE SYSTEMS, 2013, 38 (03)

[4]

From Chemical Graphs in Computer-Aided Drug Design to General Markov-Galvez Indices of Drug-Target, Proteome, Drug-Parasitic Disease, Technological, and Social-Legal Networks[J] . Pablo Riera-Fernandez,Cristian R. Munteanu,Julian Dorado,Raquel Martin-Romalde,Aliuska Duardo-Sanchez,Humberto Gonzalez-Diaz.Current Computer Aided-Drug Design . 2011 (4)

[5] A graph-theoretic analysis of the human protein-interaction network using multicore parallel algorithms [J].

Bader, David A. ;

Madduri, Kamesh .

PARALLEL COMPUTING, 2008, 34 (11) :627-639

[6]

How Reliable are Experimental Protein–Protein Interaction Data?[J] . Einat Sprinzak,Shmuel Sattath,Hanah Margalit.Journal of Molecular Biology . 2003 (5)

[7]

A graph distance metric based on the maximal common subgraph[J] . Horst Bunke,Kim Shearer.Pattern Recognition Letters . 1998 (3)

[8]

An Algorithm for Subgraph Isomorphism[J] . J. R. Ullmann.Journal of the ACM （JACM） . 1976 (1)

[9]

Graphs-at-a-time:Query language and access methods for graph data-bases. He H,Singh A K. Proc of the2008ACM SIGMOD Int Conf on Management of Data . 2008

[10]

Graph Indexing Tree+Delta＞=Graph. P. Zhao,J. X. Yu,P. S. Yu. Proceedings of the33rd International Conference on Very Large Data Bases （VLDB） . 2007

← 1 →