「DAG Reduction: Fast Answering Reachability Queries」の編集履歴（バックアップ）一覧はこちら
追加された行は緑色になります。
削除された行は赤色になります。
* DAG Reduction: Fast Answering Reachability Queries
- Junfeng Zhou, Shijie Zhou, Jeffrey Xu Yu, Hao Wei, Ziyang Chen, Xian Tang
- SIGMOD 2017
* ga
* 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）がある程度向上
--- 索引サイズ：減
--- 索引構築時間：増（提案手法の実行時間も含むため）
--- クエリ時間：減
&tags()
2017/05/27
