Top-K Nearest Keyword Search on Large Graphs
-
Miao Qiao, Lu Qin, Hong Cheng, Jeffrey Xu Yu, Wentao Tian
-
In VLDB 2013
メモ
概要
-
top-k nearest keyword search
-
頂点: 0個以上のキーワード
-
辺: 長さ
-
クエリ: ノード、キーワード、k
-
出力: キーワードを含みノードに近いkノード
-
top-k nearest keyword search に対するアルゴリズム
-
2つ提案
-
kが小さいよう
-
大きくても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
-
nc個の中心ノードをランダムサンプリング
-
Voronoi図を作成
-
dist(v, wit_O(v)) を前計算しておく
-
dist_O(u,v)を以下で推定
-
dist(u, wit_O(u)) + dist(v, wit_O(v)) (wit(u)=wit(v))
-
∞ 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
実験
比較対象
-
提案手法
-
boundk
-
pivot
-
boundk-gs
-
pivot-gs
-
BFS
-
PMI
設定
データセット
-
DBLP
-
頂点: 論文、著者、カンファレンス/ジャーナル
-
辺: ある論文の著者/あるカンファレンスに投稿した
-
キーワード: 名前、タイトル、年、とか色々
-
FLARN
クエリ
評価基準
-
hit rate
-
Spearman's rho
-
error
-
query time
-
index time
-
index size
結果
error
query time
-
PMIが一番速い
-
でも提案手法も3msとかそんなもん(k=128)
まとめ(まだちゃんと読んでないけど
-
問題としては面白そう
-
データも普通にでかい
-
距離に保証があるのは強い?なあ
-
あんまり既存手法が無いんだったらいいかも?
VLDB nearest keyword
2013-10-17 23:38:18 (Thu)
最終更新:2013年10月17日 23:38