基于频繁闭图的图包含查询算法  

A Closed Frequent Subgraph Based Containment Query Algorithm

作　　者：李先通[1] 安实[1] 

机构地区：[1]哈尔滨工业大学交通科学与工程学院,黑龙江哈尔滨150000

出　　处：《电子学报》2010年第12期2937-2943,共7页Acta Electronica Sinica

摘　　要：交通网络可利用图数据进行描述与分析,常用的方法包括挖掘、查询、分类等.提高大规模图集上查询算法效率的问题是当前图数据分析领域中一个重要的研究方向.给定图集,图包含查询返回图集中所有查询图的子图.本文提出一种基于频繁闭图的包含查询算法.算法首先通过选择比消除频繁闭图之间的冗余,然后将具有强选择性的频繁闭图通过树的结构组织起来建立索引,并在此索引基础上实现图包含查询.在文章的最后,给出了理论与实验的分析结果.结果表明,该算法不但能高效的进行索引筛选,而且能显著的减小候选集尺寸,进而大大的降低了查询图与索引模式之间以及与候选集之间的子图同构测试次数,提高了查询效率.Transportation network can be well described and analyzed through graph data. The analyzing methods include mine, query, and classification, etc. The improvement on the efficiency of scalable algorithms on large graph dataset is important in graph analyzing. Given a graph dataset and query graph, graph containment query retrieves graphs from the dataset which are subgraphs of query graph. In this paper, a frequent closed subgraph （CFG） based graph containment query algorithm is proposed. The algorithm selects discriminative-redundancy-aware CFG to build a tree structure index, which satisfies such query. Theoretical analysis and experimental evaluation are presented at the end. The results show that this algorithm is not only filtering out correlated indexed features efficiently, but also reducing subgraph isomorphism tests between query graph and indexed features effectively.

关 键 词：交通网络 图数据库 图索引 包含查询 频繁子图 

分 类 号：TP311.131[自动化与计算机技术—计算机软件与理论]