Efficient and Accurate Query Evaluation on Uncertain Graphs via Recursive ...

Efficient and Accurate Query Evaluation on Uncertain Graphs via Recursive Stratified Sampling

  • Rong-Hua Li, Jeffrey Xu Yu, Rui Mao, Tan Jin
  • ICDE 2014

概要

  • よくある期待値クエリ評価と閾値クエリ評価を計算したい
  • 愚直のMonte-Carloは分散が悪いので、
  • 階層的な標本をする推定器を提案
  • 影響力評価と期待信頼距離クエリに応用

解く問題

  • クエリ頂点q、何らかの評価関数φq(G)
  • 期待値クエリ $$ \mathbf{E}_{G \sim \mathcal{G}}[\phi_q(G)] $$
  • 閾値クエリ $$ \mathbf{Pr}_{G \sim \mathcal{G}}[\phi_q(G) > \delta] $$
  • 例: 信頼性計算、期待値信頼距離、影響拡散、距離制限到達性

提案手法

  • 簡単に言うと、一部の辺の状態を固定して、再帰する
  • 再帰の停止条件は「サンプルサイズ<τ」or「自由辺数<r」
  • 辺の選び方
    • ランダムかクエリ頂点からBFSした奴…とか

Class-I

  • Basic stratified estimator
  • r辺選ぶ→2^r事象生成→各々の事象についてサンプリング
  • 事象iのサンプルサイズ
    • ベスト: (全体のサンプルサイズ)*Pr[i]*(iの標準偏差) ←分からん□
    • しょうがないにゃあ: (全体のサンプルサイズ)*Pr[i] ←分散は増えない
  • Recursive stratified estimator
  • 各々の事象からさらに再帰
  • ぶっちゃけあまり意味ない

Class-II

  • r辺選び、r+1事象生成
  • こんな感じ: 0000, 1***, 01**, 001*, 0001
    • *は未定
  • Basic stratified estimator
  • サンプルサイズの設定とかはClass-Iと同じ
  • Recursive stratified estimator
  • 再帰の仕方も同じ

Cut-based estimator

  • カット(ただしカットではない)集合C: C中の辺の状態が0だと、φが定数
    • 影響拡散ならシードの出辺、期待信頼距離なら始点の出辺
  • |C|事象生成: 1***, 01**, 001*, 0001
  • あとはほぼ上のと同じ
    • 再帰する時は、影響拡散や期待信頼距離の場合、ほんのちょっとだけ考える必要あり
  • 良くなりそうな見込みはあるらしい

実験

  • ベースライン手法: 愚直Monte-Carlo、RSS-I with RM (r=1)
  • 提案手法: {BSS-I, RSS-I, BSS-II, RSS-II}×{RM, BFS}とBCSS・RCSS
  • 色々やったよ!RCSSが一番良いね!!!!!!

まとめ

  • 分散一応減ってるけど微妙すぎ…
  • 確率の設定をよく考えると普通にサンプリングした時と漸近的には(?)同じでは?
  • サンプル数をかなり上げたらあまり変わらないような…。

ICDE uncertain graphs 情報拡散 最短経路

2017/01/04 2017/01/04

最終更新:2017年01月04日 17:56