Dr. Darrell Long

Compressing Provenance Graphs

Proceedings of the Workshop on the Theory and Practice of Provenance (TaPP)

June 2011View full paper

Abstract

The provenance community has built a number of systems to collect provenance, most of which assume that provenance will be retained indefinitely. However, it is not cost-effective to retain provenance information inefficiently. Since provenance can be viewed as a graph, we note the similarities to web graphs and draw upon techniques from the web compression domain to provide our own novel and improved graph compression solutions for provenance graphs. Our preliminary results show that adapting web compression techniques results in a compression ratio of 2.12:1 to 2.71:1, which we can improve upon to reach ratios of up to 3.31:1.

BibTeX

@inproceedings{xie-tapp11,
  author       = {Yulai Xie and Kiran-Kumar Muniswamy-Reddy and Darrell D. E. Long and Ahmed Amer and Dan Feng and Zhipeng Tan},
  title        = {Compressing Provenance Graphs},
  booktitle    = {Proceedings of the Workshop on the Theory and Practice of Provenance (TaPP)},
  organization = {Usenix Association},
  address      = {Crete},
  month        = jun,
  year         = {2011}
}
View full paper