###
DOI:
Journal of Software:2009.20(zk):144-153

基于最小生成树的图数据库索引算法
李楠,高宏,李建中
(哈尔滨工业大学 计算机科学与技术学院,黑龙江 哈尔滨 150001)
Minimal Spanning Tree Based Graph Indexing Algorithm
LI Nan,GAO Hong,LI Jian-Zhong
()
Abstract
Chart / table
Reference
Similar Articles
Article :Browse 3772   Download 3930
Received:May 01, 2009    Revised:July 20, 2009
> 中文摘要: 对复杂数据进行图模式建模近几年越来越流行,因此,在查询执行的优化过程中图索引技术变得至关重要.研究了图模式的索引问题,并且提出了一种近似的索引方法,称为MSTA方法.MSTA方法利用最小生成树结构作为索引特征,依据最小生成树边序列的包含关系和基于最大公共子图的图距离度量,将最小生成树组织到一个称为MST树的索引结构中.MST树索引结构可以高效地支持多种查询,例如子图查询.MSTA方法具备高效的索引性能.在索引大小和索引建立时间方面,传统方法是MSTA方法的数十倍,甚至上百倍.MSTA方法虽然不能返回完整结果,但是可以返回经图距离度量排序最好的部分结果.
中文关键词: 图数据库  图索引  近似算法  子图查询
Abstract:Graphs have become popular for modeling structured data. As a result, graph indexing technique has come to play an essential role in query processing. This paper investigates the issues of indexing graphs and propose an approximation solution. The proposed approach, called MSTA, makes use of minimal spanning tree as basic indexing feature. By containment relation of edge lists and maximal common subgraph based graph distance, those minimal spanning trees are organized into an indexing structure named MST tree. MST tree can support many kinds of queries efficiently, such as subgraph queries. The performance study shows that index size and constructing time of traditional methods are tens or even a hundred times larger than MSTA.
文章编号:     中图分类号:    文献标志码:
基金项目:Supported by the National Natural Science Foundation of China under Grant Nos.60933001, 60773063 (国家自然科学基金); the National Basic Research Program of China under Grant No.2006CB303000 (国家重点基础研究发展计划(973)) Supported by the National Natural Science Foundation of China under Grant Nos.60933001, 60773063 (国家自然科学基金); the National Basic Research Program of China under Grant No.2006CB303000 (国家重点基础研究发展计划(973))
Foundation items:
Reference text:

李 楠,高 宏,李建中.基于最小生成树的图数据库索引算法.软件学报,2009,20(zk):144-153

LI Nan,GAO Hong,LI Jian-Zhong.Minimal Spanning Tree Based Graph Indexing Algorithm.Journal of Software,2009,20(zk):144-153