satoudosuのブックマーク - はてなブックマーク

大規模グラフデータベースの類似度検索ソフトウェア(gWT:graph-indexing wavelet tree)を公開しました - Yasuo Tabeiの日記

昨日のブログで紹介した大規模グラフの類似度検索の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

satoudosu 2011/06/22

research
ml

リンク

Linear Graph Miner: 線形グラフのマイニングアルゴリズム - Yasuo Tabeiの日記

データマイニングの国際会議 PAKDD2011に線形グラフのマイニングアルゴリズムに関する論文がアクセプトされました。本研究は、PFIの岡野原さん(@hillbig)、産総研の廣瀬さん、津田さん(@kojitsuda)との共同研究です。論文をarxiv.orgにアップしました。 LGM: Mining Frequent Subgraphs from Linear Graphs, Yasuo Tabei, Daisuke Okanohara, Shuichi Hirose, Koji Tsuda, The 15th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD2011), link to the paper 線形グラフ(Linear Graph)とは、通常のグラフの頂点に順序がついたグラフです(下

satoudosu 2011/06/22

research
ml

リンク

研究紹介 - SketchSort（スケッチソート）法 - Yasuo Tabeiの日記

SketchSort(スケッチソート)法の論文が ACML2010にアクセプトされました。今年も採択率30%の難関でした。 http://sugiyama-www.cs.titech.ac.jp/ACML2010/ Yasuo Tabei, Takeaki Uno, Masashi Sugiyama, Koji Tsuda: Single Versus Multiple Sorting in All Pairs Similarity Search, The 2nd Asian Conference on Machine Learning (ACML2010), Tokyo, Japan, 2010. Link to the paper SketchSort法は、データー点の集合が与えられたら、集合中の２点間の距離がある閾値以内のペアー(近傍ペアー)を全て求める問題(全点間類似度検索)を高速

satoudosu 2011/06/22

research
ml

リンク

SACHICA(類似文字列列挙アルゴリズム) - Yasuo Tabeiの日記

SACHICA(類似文字列列挙アルゴリズム)のC++による実装を公開しました。 http://sites.google.com/site/yasuotabei/sachica sachicaは、同じ長さの文字列集合を入力として、ハミング距離がある閾値以下のすべてのペアーを超高速に出力します。　アルゴリズムは、マルチソーティングという手法に基づきます。詳しくは、ハミング距離がd以内で長さがmの文字列集合があったとします。初めに、各文字列をk (> d)の部分文字列のブロックに分割します。今、ハミング距離がd以内の文字列のペアーを求めたいので、もし、ハミング距離がd以内の文字列のペアーが存在すれば、鳩の巣原理により、それらにはk - d個の完全一致するブロックが存在します。この原理に基づき、sachicaはcombination(k, k-d)のすべての組み合わせのブロックをラディックスソ

satoudosu 2011/06/22

research

リンク

Yasuo Tabeiの日記

SketchSortとは全ペアー類似度検索(与えられたデータセットからすべての類似するデータペアーを発見する問題)を高速に解くためのソフトウェアーで、以前に論文とソフトウェアーを公開しました。論文: Yasuo Tabei, Takeaki Uno, Masashi Sugiyama, Koji Tsuda: Single Versus Multiple Sorting in All Pairs Similarity Search, The 2nd Asian Conference on Machine Learning (ACML), Tokyo, Japan, 2010. ソフトウェアー: https://code.google.com/archive/p/sketchsort ブロブ記事: http://d.hatena.ne.jp/tb_yasu/20100911/1284207