Evaluating Multi-Way Joins over Discounted Hitting Time - todo314 @ ウィキ

Evaluating Multi-Way Joins over Discounted Hitting Time

• Wangda Zhang, Reynold Cheng, Ben Kao
• ICDE 2014

概要

• random walkに基づくスコアのでかいtop-k n-tupleを返す問題の提案
• それに対する色々な枝刈りを詰めまくった手法を提案
• 実験的に相当早くなった

top-k n-way joins 定義

• 入力
• グラフ: G=(V_G, E_G)
• クエリグラフ: Q=(V_Q, E_Q)
  • V_Q=(R_1, …, R_n)
  • R_i⊆V_G
• 単調集計関数: f: R^|E_Q|→R
  • maxとかminとか+とか重み付けとか…
• k
• DHT関数 h のパラメータ
• 出力
• 辺e∈E_QのDHTスコアh_eを集計した値の大きいtop-kのn-tuple
  • f(h_e1, …, h_em)

提案手法

ナイーブな手法

• Nested Loop(NL)…オワコン
• All Pairs(AP)…オワコン

Partial Join

• 辺e=(R_i, R_j)についてh(p∈R_i, q∈R_i)の高いtop-mのペア(p,q)を前計算
• その後，top-mのペアを上手いこと合併してtop-k n-tupleを構築
• どっかの辺の(p,q)を今とってきたとすると
• それにマッチするようなn-tupleを適当に探索する
• ペアを高い順に見ていく+fは単調だから上手くいく
• この辺りはPull/Bound Rank JoinというPODSの手法
• mが小さくてペアが足りなくなった or top-kのn-tupleを保証できなかったら？
  • (m+1)に拡張する→Incremenatl Partial Join

DHTの計算

• $$ h(u, v) = \alpha \sum_{i=1}^{\infty}\lambda^i P_i(u, v) + \beta $$
  • P_i(u, v): uからrandom walkした時iステップ目でvに到達する確率
• 本当は無限ステップまでやるけど無理なので，dステップ目までで妥協
• 一応指数減衰だから上・下限は出せる
• Lemma 1の関係が逆転しててマジ基地

Forward Basic Join

• 各(p,q)についてDP
• O(|P||Q|d|E_G|)でオワコン
• Iterative Deepening Joinを追加
  • hの上・下限を見積もりながら枝刈り

Backward Basic Join

• 各qについて逆からDPして全pについて一気にもとめる
• O(|Q|d|E_G|)で|P|倍速い
• Iterative Deepening Joinを追加
• 上・下限を見積もって枝刈り
  • 無限和のP_iを1としたりちょっと頑張ってみたりでXとYの2種類

Incremenatl Partial Join

• ナイーブにtop-(m+1)を求めなおすとヤバい
• ↑の枝刈り途中の結果を再利用する

実験

• 色々手法を提案しまくったので，それに対して逐一比較していく
• 割りと早くなったらしい
• 面倒なので省略（見れば分かる

まとめ

• かなりごちゃごちゃしてた
• とにかく手法を見せたいんだな～と思った（データベースだし
• PODSのEvaluating Rank Joins with Optimal Costは見る価値があるかもしれん

ICDE random walk

2014-06-09 19:38:07 (Mon)