Dr. Darrell Long

A Hybrid Approach for Efficient Provenance Storage

Proceedings of International Conference on Information and Knowledge Management (CIKM)

October 2012View full paper

Abstract

Efficient provenance storage is an essential step towards the adoption of provenance. In this paper, we analyze the provenance collected from multiple workloads with a view towards efficient storage. Based on our analysis, we characterize the properties of provenance with respect to long term storage. We then propose a hybrid scheme that takes advantage of the graph structure of provenance data and the inherent duplication in provenance data. Our evaluation indicates that our hybrid scheme, a combination of web graph compression (adapted for provenance) and dictionary encoding, provides the best tradeoff in terms of compression ratio, compression time and query performance when compared to other compression schemes.

BibTeX

@inproceedings{xie-cikm12,
  author       = {Yulai Xie and Kiran-Kumar Muniswamy-Reddy and Dan Feng and Yan Li and Darrell D. E. Long and Zhipeng Tan and Lei Chen},
  title        = {A Hybrid Approach for Efficient Provenance Storage},
  booktitle    = {Proceedings of International Conference on Information and Knowledge Management (CIKM)},
  organization = {ACM},
  address      = {Maui},
  month        = oct,
  year         = {2012}
}
View full paper