On Querying Historical Evolving Graph Sequences (VLDB'11)

• モチベーション
  • Evolving Graph Sequence (EGS)
    • large, numerous, gradually evolving
  • 今の解析は static ばっかりだけど dynamic もやろう
  • 最短路，（近接）中心性
    • ある一点，とかでなく，「どう変化したか」という種類のクエリのみ
• 手法
  • グラフ間の類似度を定義
  • ある程度（類似度パラメータα）似ている間，というのをひとまとめの区間（クラスタ）だと思う
  • 最短路
    • 再計算の必要がないことの十分条件を判定できるようにする
    • 変化の可能性が無ければそのまま，変化の可能性があれば BFS する
    • よく見るとεというのが入っていて，エラーがあるらしい？
  • 近接中心性
• Storage Models (謎)
• 実験
  • インデクシング早い（２分とか），クエリは１０秒とか
  • インデックスは数百MB
  • εについての言及無し