並列組織化アルゴリズムによるグラフマッチングと部分構造の 発見手法

前原 恵太  上原 邦昭  

誌名
電子情報通信学会論文誌 D   Vol.J82-D1   No.1   pp.111-120
発行日: 1999/01/25
Online ISSN: 
DOI: 
Print ISSN: 0915-1915
論文種別: 特集論文 (高度データベース論文特集)
専門分野: 並列アルゴリズム
キーワード: 
グラフマッチング,  MDL基準,  並列処理,  組織化アルゴリズム,  

本文: PDF(559.1KB)>>
論文を購入




あらまし: 
グラフによるデータ表現は非常に柔軟性があり,さまざまな分野で用いられている. 中でも,グラフ集合の中から重要な意味をもつ構造を発見したり, 与えられたグラフにマッチする部分グラフを検索するなど, 基本的な処理を高速に行うアルゴリズムを開発することは非常に重要である. しかし,対象となるグラフ数が増大すると,処理に必要な計算コストが爆発するという問題がある. 本論文では,ラベル付き有向グラフの集合から複数のグラフが共通してもつ部分構造を発見し, 発見された構造に基づいてネットワークとして組織化するアルゴリズムについて述べる. なお,本アルゴリズムでは, MDL(Minimum Description Length)基準を用いたヒューリスティックスにより処理を高速化している.