Keyword-aware Optimal Route Search - todo314 @ ウィキ

Keyword-aware Optimal Route Search

• Xin Cao Lisi Chen Gao Cong Xiaokui Xiao
• In VDLB 2012

メモ

• Y.Kawata

問題

• クエリ
  • 始点・終点
  • キーワードの集合
  • budget上限
• 目標
  • キーワードをすべてカバー
  • 経路のbudgetがbudget上限を超えない
  • objective最小化

モチベーション

• 旅行とか

計算量クラス

• NP-hard
• せやな

アルゴリズム

前処理

• (u, v)について
  • objective score 最小経路
  • budget score 最小経路

OSScaling

• 状態ラベル
  • 経路
  • いろいろスコア
• よさげなものから見る
• ちょこちょこ枝刈り
• スコアをてきとーにスケーリング

BucketBound

• スコアでバケットに分離してゴニョゴニョ

Greedy

• マジ適当

実験

• Flickr
• road network
  • ちょっと適当？

まとめ

• もちょっと改善できそうだ
• スコア謎過ぎワロタリオン

VLDB routing

2013-10-17 23:40:03 (Thu)