Distributed Set Reachability - todo314 @ ウィキ

Distributed Set Reachability

• Sairam Gurajada, Martin Theobald
• SIGMOD 2016

概要だけ

• S-T間で到達可能な頂点対を並列計算で頑張る
• 並列の意味…頂点集合の分割＋カット
• 並列到達可能性"s→t?"[Fang-Wang-Wu. VLDB'12]
  • Master-Slave
  • Slave: (Giに入る)×(Giから出る)で到達可能な頂点対を計算
    • sやtがある場合
  • Master: Slaveの情報とカット情報を元に判定
    • カットだけなるグラフは小さいはず
• 頑張った所: 到達可能な意味で同じ部分をまとめる、とかして事前にいい感じのを作る
• 色々と微妙

SIGMOD 分散並列 到達可能性

2016/12/15