大規模グラフデータベースの類似度検索ソフトウェア(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を指定しています。

*1:注意:google web toolkitではない