Pushing the Envelope in Graph Compression - todo314 @ ウィキ

Pushing the Envelope in Graph Compression

• Panagiotis Liakos, Katia Papakonstantinopoulou, Michael Sioutis
• CIKM 2014

概要

• Pushing the Envelope: 限界に挑む（慣用句）
• グラフ圧縮の限界
• 隣接行列がある
  • 対角成分付近を圧縮する手法を提案
  • 残りは既存手法

調査

• 隣接行列のヒートマップを見てみると，対角成分付近に集中しているっぽいぞ
  • ID付けはそのまんまで前処理無しらしい
• 良さそうに並び替える問題も研究されているらしい…

提案手法

• 対角成分の前後kの要素を圧縮するよ
• 各行は，長さ2k+1の01ベクトル
• 2^{2k+1}のパターン数を数える
• (パターン,個数)は極端に状態数が多くない？ので，いい感じに圧縮できそう
  • 詳細略

CIKM グラフ圧縮

2014/11/27