iRoad: A Framework For Scalable Predictive Query Processing On Road Networks - todo314 @ ウィキ

iRoad: A Framework For Scalable Predictive Query Processing On Road Networks

• Abdeltawab M. Hendawi, Jie Bao, and Mohamed F. Mokbel
• In VLDB
• 2013

メモ

• 何となくこんなのも読んでみる
• ミネソタ大学の人々

概要

• IRoad フレームワークというものを作った
  • 動くオブジェクトの予測クエリ
• 予測クエリ
  • 点予測
  • 範囲予測
  • KNN予測
  • 集団予測
• データ構造reachability tree
  • 時間T以内に到達可能なノードを保持（？）
  • 仮定: オブジェクトは最短経路を通る
  • 大体30分
• 数M頂点の道路ネットワークにスケールする

Overview

クエリ

点予測

• 入力:
  1. オブジェクトの集合 O
  2. 道路ネットワーク G=(V,E,W) (Wは時間)
  3. 最大予測時間 T
  4. 予測点クエリ Q(v,t)
     • v: Vの頂点
     • t: T以下
• 出力
  1. オブジェクトの集合 R
     • 頂点vに時間t以内に現れそう
  • 例 R(Q(v3, 30)) = {<O1, 0.8>}
    • O1というオブジェクトが30分以内にv3に現れる確率は0.8

仮定

• オブジェクトは最短経路を通る
• Tの値は（平均の旅行時間19分により）boundされる

拡張

範囲予測

• 入力が頂点の「集合」

KNN 予測

• 確率の順にK個出力

集団予測

• オブジェクトの数を返す

データ構造

道路ネットワーク

到達可能木(reachability tree)

• T以内に辿り着ける頂点を保持

旅行履歴

reachability trees

• オブジェクトOiがvに時刻tにいる
• 1/a
  • a: オブジェクトが今いるノードuの下の部分木のノード数

構築

• 最良優先探索
• T
• ε: [0,T]
  • 木の深さを決定づける
  • ε小: 容量は食わない、クエリが遅い
  • ε大: 容量は食う、クエリが速い

movement handler

まとめ

• なんかよくわからん

VLDB

2013-10-07 17:34:50 (Mon)