C++によるQeury Suggestion Algorithmのいくつかの実装です。
現状では以下のアルゴリズムを実装しています。
- Pan J, Yang H, Faloutsos C, Duygulu P. Automatic multimedia cross-modal correlation discovery. Proceedings of the 2004 ACM SIGKDD international conference on Knowledge discovery and data mining - KDD '04. 2004:653.
- Deng H, King I, Lyu MR. Entropy-biased models for query representation on the click graph. Proceedings of the 32nd international ACM SIGIR conference on Research and development in information retrieval - SIGIR '09. 2009:339.
- Kong H, Lyu MR, King I. A generalized Co-HITS algorithm and its application to bipartite graphs. Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining - KDD '09. 2009:239.
- Mei Q, Zhou D, Church K. Query suggestion using hitting time. Proceeding of the 17th ACM conference on Information and knowledge mining - CIKM '08. 2008:469.
tr1::unordered_mapに依存しています。
また、テストにはgoogletestを用いています。 $make main $ruby ./run.rb 実行時にいくつかの引数を指定することができます。 省略時の初期値はconfig.yamlに記載しているので、そのまま書き換える事も可能です。
-
-i:入力ファイルの指定。省略不可。
-
-o:出力ファイルの指定。省略時は入力ファイルと同フォルダに出力。
-
-q:対象とするクエリ。省略不可。
-
-m:用いるアルゴリズムの選択。省略時は1。それぞれ 1 => Random walk With Restart(RWR)
2 => Entropy biased models
3 => Generalized Co-HITS
4 => hitting timeに対応にしています。
-
-t:random walkの繰り返し回数。省略時は5
-
-d:サブグラフを作る際の深さ。省略時は4
-
-s:出力する際の件数。省略時は10
-
-e:CF-IQFに基づいて遷移確率を上書きするか。省略時はfalse。アルゴリズムが2の場合はtrueに。
-
-u:Generalized Co-HITSで用いる伝播パラメータ。省略時は0.5
-
-v:Generalized Co-HITSで用いる伝播パラメータ。省略時は0.5
-
-c:RWR、Entropy biased modelsで用いるダンピングファクター。省略時は0.5
入力ファイルのフォーマットはタブ区切りで以下のようなものになります。 query url count(整数) 例として google www.google.com 100 google www.gmail.com 45 google mail www.gmail.com 45 google メール www.gmail.com 53 といった形になります。