DAG Reduction: Fast Answering Reachability Queries - todo314 @ ウィキ

DAG Reduction: Fast Answering Reachability Queries

• Junfeng Zhou, Shijie Zhou, Jeffrey Xu Yu, Hao Wei, Ziyang Chen, Xian Tang
• SIGMOD 2017

概要

• 到達可能性クエリを高速に応えるためのグラフの前処理を考える．
• ◯最も基本的な処理 = SCCを潰しDAGにする
  • これだけでは不十分なので，以下の"DAG reduction"を考え，
  • 到達可能性を失わずにグラフを更に小さく（し，既存の到達可能性クエリ手法を適用）する．
• ◯Transitive reduction (TR)
  • 目標:Transitive closureを保持したまま辺を削除する．
  • 著者が提案したLPM treeという木を作り，
  • 「元のグラフの上での子孫」と「木の上での子孫」を
  • 器用に利用し，冗長な辺（(u,w)が冗長…(u,w)を消してもuからwに到達可能）を判定し，削除していく．
• ◯Equivalence reduction (ER)
  • 目標:2頂点u,vについて，
  • 　条件: (uの先祖)=(vの先祖)かつ(uの子孫)=(vの子孫)
  • ならば，uとvを同一視する．
  • 既存のER手法は，ほぼ明示的に先祖・子孫を求めているため，時間・空間共にグラフサイズの二乗であったが，
  • TRを適用後のグラフでは，条件の判定が高速に行える(Lemma 4.1)ため，全体でalmost linear-timeにまで速くなった.

• 実験
  • 20グラフデータセット: <25M頂点・<40M辺
  • TRでは，提案手法が既存手法よりも速度が優れている
  • ERでも，提案手法が既存手法よりも速度が優れている
  • 到達可能性クエリの索引手法（GRAIL, FELINE, IP+, PLL, TF）がある程度向上
    • 索引サイズ：減
    • 索引構築時間：増（提案手法の実行時間も含むため）
    • クエリ時間：減

SIGMOD 到達可能性 到達可能性クエリ

2017/05/27