Minimal Spanning Tree Based Graph Indexing Algorithm
DOI:
Author:
Affiliation:

Clc Number:

Fund Project:

  • Article
  • |
  • Figures
  • |
  • Metrics
  • |
  • Reference
  • |
  • Related
  • |
  • Cited by
  • |
  • Materials
  • |
  • Comments
    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.

    Reference
    Related
    Cited by
Get Citation

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

Copy
Share
Article Metrics
  • Abstract:
  • PDF:
  • HTML:
  • Cited by:
History
  • Received:May 01,2009
  • Revised:July 20,2009
  • Adopted:
  • Online:
  • Published:
You are the firstVisitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-4
Address:4# South Fourth Street, Zhong Guan Cun, Beijing 100190,Postal Code:100190
Phone:010-62562563 Fax:010-62562533 Email:jos@iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063