KDD2015 Panther: Fast Top-k Similarity Search on Large Networks読んだ
どんなもの？
ネットワーク上の類似ノードTop Kを高速に検索する手法を提案
先行研究と比べると？
300倍早くなった
技術や手法のキモはどこ？
- サンプリングで近似してやることで高速化した
- random pathという考え方に基づいている R回長さTのランダムウォークを行う。もし二つの接点が似ているなら同一のパスに出てくる確率が高くなるはず、というアイデア
どうやって有効だと検証した？
- R,T,エラーのバウンド,信頼水準の関係を導出した
- マイクロブログと共著ネットワークで速度・精度を比較
ref
メモ
https://research.preferred.jp/2011/08/nearest_neighbor_search2011/
Efficient K-Nearest Neighbor Graph Construction for Generic Similarity Measuresとやってることは同じっぽい