読者です 読者をやめる 読者になる 読者になる

On Querying Historical Evolving Graph Sequences (VLDB'11)

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