大規模グラフデータベースの類似度検索ソフトウェア(gWT:graph-indexing wavelet tree)を公開しました
昨日のブログで紹介した大規模グラフの類似度検索のC++による実装(gWT:graph-indexing wavelet tree*1 )を公開しました。googlecodeよりダウンロードすることができます。
初めに、gWTはgwt-buildによりグラフデータベースの索引付けを行います。以下にサンプルを示します。
./gwt-build -iteration 2 ../dat/mutagen.gsp index
この例では、mutagen.gspが入力のグラフデータベースファイルで、indexが索引の出力ファイルです。-iterationオプションでは、Weisfeiler-Lehman手続きのイテレーション回数を指定します。ここでは２回に指定しています。入力ファイルの形式は、各行がノードラベルまたはエッジラベルとノードとの接続関係を表現します。各行の意味は以下を参照してください。
"t # N" はN番目のグラフであることを表します。 "v M L"はM番目の頂点がラベルLを持つことを表しています。 "e P Q L"はQ番目の頂点とL番目の頂点がエッジで結ばれていて、エッジラベルはLであることを表しています。 M, N, P, Q, Lは正の整数値です。
gwt-buildから作成した索引からクエリーグラフを検索する場合はgwt-searchを使います。
./gwt-search -kthreshold 0.8 index ../dat/mutagen_query.gsp
indexはgwt-buildより作成した索引ファイルです。mutagen_query.gspはクエリーグラフのファイルで上記で示した形式と同様です。-kthresholdにより類似度の閾値（０から1の値）を指定します。ここでは、0.8を指定しています。
