iRoad: A Framework For Scalable Predictive Query Processing On Road Networks
-
Abdeltawab M. Hendawi, Jie Bao, and Mohamed F. Mokbel
-
In VLDB
-
2013
メモ
概要
-
IRoad フレームワークというものを作った
-
予測クエリ
-
データ構造reachability tree
-
時間T以内に到達可能なノードを保持(?)
-
仮定: オブジェクトは最短経路を通る
-
大体30分
-
数M頂点の道路ネットワークにスケールする
Overview
クエリ
点予測
-
入力:
-
オブジェクトの集合 O
-
道路ネットワーク G=(V,E,W) (Wは時間)
-
最大予測時間 T
-
予測点クエリ Q(v,t)
-
出力
-
オブジェクトの集合 R
-
例 R(Q(v3, 30)) = {<O1, 0.8>}
-
O1というオブジェクトが30分以内にv3に現れる確率は0.8
仮定
-
オブジェクトは最短経路を通る
-
Tの値は(平均の旅行時間19分により)boundされる
拡張
範囲予測
KNN 予測
集団予測
データ構造
道路ネットワーク
到達可能木(reachability tree)
旅行履歴
reachability trees
-
オブジェクトOiがvに時刻tにいる
-
1/a
-
a: オブジェクトが今いるノードuの下の部分木のノード数
構築
-
最良優先探索
-
T
-
ε: [0,T]
-
木の深さを決定づける
-
ε小: 容量は食わない、クエリが遅い
-
ε大: 容量は食う、クエリが速い
movement handler
まとめ
VLDB
2013-10-07 17:34:50 (Mon)
最終更新:2013年10月07日 17:34