Top-K Nearest Keyword Search on Large Graphs - todo314 @ ウィキ

Top-K Nearest Keyword Search on Large Graphs

• Miao Qiao, Lu Qin, Hong Cheng, Jeffrey Xu Yu, Wentao Tian
• In VLDB 2013

メモ

• Jeffrey Xu Yu!!

概要

• top-k nearest keyword search
  • 頂点: 0個以上のキーワード
  • 辺: 長さ
  • クエリ: ノード、キーワード、k
  • 出力: キーワードを含みノードに近いkノード
• top-k nearest keyword search に対するアルゴリズム
  • 最短経路木
• 2つ提案
  1. kが小さいよう
  2. 大きくてもOK

応用

• Facebook、hikingが好きな20人を探すというのは、なんか使える
• 近い店を列挙

既存手法

• Partitioned Multi-Indexing (PMI)
• distance oracle
• 2log2|V|-1 近似
  • あんまり良くない

問題定義

• クエリ: Q=(q,λ,k)
  • q: クエリノード
  • λ: キーワード
  • k: 正整数
• 結果: R={v1, v2, …, vk} or {v1:dist(q,v1), v2:dist(q,v2), …, vk:dist(q,vk)}
  • vi: λを∈
  • λを含みviより近いノードは存在しない

Distance Oracle

• O: distance oracle

1. nc個の中心ノードをランダムサンプリング
2. Voronoi図を作成
   • wit_O(v): vが属する中心ノード
3. dist(v, wit_O(v)) を前計算しておく
4. dist_O(u,v)を以下で推定
   1. dist(u, wit_O(u)) + dist(v, wit_O(v)) (wit(u)=wit(v))
   2. ∞ otherwise

• どう考えてもよくないだろ、いい加減にしろ！
  • r=p log|V| 個のoracleを作る
  • r個のクエリの内一番小さいものを出力する
  • p=Θ|V|^{1/log|V|}なら 2log2|V|-1 以内の答えがかえってくる

PMI distance oracleによるk-NK

• めっちゃ単純
• qが属するセンターを見つけて、u1->c->qの距離順にk個とる
• oracleがr個あるので、k個だけ残すようにマージしていく

Exact 1-NK on a Tree

• 1個だけほしい

実験

比較対象

• 提案手法
  • boundk
  • pivot
  • boundk-gs
  • pivot-gs
• BFS
  • Dijkstraやるだけ
• PMI
  • state-of-the-art

設定

• r=log2|V|

データセット

• DBLP
  • 頂点: 論文、著者、カンファレンス/ジャーナル
  • 辺: ある論文の著者/あるカンファレンスに投稿した
  • キーワード: 名前、タイトル、年、とか色々
• FLARN

クエリ

• 500クエリ
• k=1,2,…,128

評価基準

• hit rate
• Spearman's rho
• error
• query time
• index time
• index size

結果

error

• 提案手法がPMIに比べて圧倒的に良い

query time

• PMIが一番速い
• でも提案手法も3msとかそんなもん(k=128)

まとめ（まだちゃんと読んでないけど

• 問題としては面白そう
  • 結構一般的だし
• データも普通にでかい
• 距離に保証があるのは強い？なあ
• あんまり既存手法が無いんだったらいいかも？

VLDB nearest keyword

2013-10-17 23:38:18 (Thu)