SPARTAN: using constrained models for guaranteed-error semantic compression

ABSTRACT

While a variety of lossy compression schemes have been developed for certain forms of digital data (e.g., images, audio, video), the area of lossy compression techniques for arbitrary data tables has been left relatively unexplored. Nevertheless, such techniques are clearly motivated by the ever-increasing data collection rates of modern enterprises and the need for effective, guaranteed-quality approximate answers to queries over massive relational data sets.In this paper, we propose SPARTAN, a system that takes advantage of attribute semantics and data-mining models to perform lossy compression of massive data tables. SPARTAN is based on the novel idea of exploiting predictive data correlations and prescribed error-tolerance constraints for individual attributes to construct concise and accurate Classification and Regression Tree (CaRT) models for entire columns of a table. More precisely, SPARTAN selects a certain subset of attributes (referred to as predicted attributes) for which no values are explicitly stored in the compressed table; instead, concise error-constrained CaRTs that predict these values (within the prescribed error tolerances) are maintained. To restrict the huge search space of possible CaRT predictors, SPARTAN uses a Bayesian network structure to guide the selection of CaRT models that minimize the overall storage requirement, based on the prediction and materialization costs for each attribute. SPARTAN's CaRT-building algorithms employ novel integrated pruning strategies that take advantage of the given error constraints on individual attributes to minimize the computational effort involved. Our experimentation with several real-life data sets offers convincing evidence of the effectiveness of SPARTAN's model-based approach --- SPARTAN is able to consistently yield substantially better compression ratios than existing semantic or syntactic compression tools (e.g., gzip) while utilizing only small samples of the data for model inference.

REFERENCES

• 1: "NetFlow Services and Applications". Cisco Systems, 1999.
• 2: Shivnath Babu , Minos Garofalakis , Rajeev Rastogi, SPARTAN: a model-based semantic compression system for massive data tables, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.283-294, May 21-24, 2001, Santa Barbara, California, United States
• 3: Leo Breiman, Jerome H. Friedman, Richard A. Olshen, and Charles J. Stone. "Classification and Regression Trees". Chapman & Hall, 1984.
• 4: Adam L. Buchsbaum , Donald F. Caldwell , Kenneth W. Church , Glenn S. Fowler , S. Muthukrishnan, Engineering the compression of massive tables: an experimental approach, Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, p.175-184, January 09-11, 2000, San Francisco, California, United States
• 5: Scott Davies , Andrew Moore, Bayesian networks for lossless dataset compression, Proceedings of the fifth ACM SIGKDD international conference on Knowledge discovery and data mining, p.387-391, August 15-18, 1999, San Diego, California, United States [doi>10.1145/312129.312289]
• 6: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 7: C. Goh, K. Aisaka, M. Tsukamoto, K. Harumoto, and S. Nishio. "Data Compression with Data Mining Methods". In Proc. of the 5th Intl. Conf. on Foundations of Data Organization (FODO), November 1998.
• 8: Jonathan Goldstein , Raghu Ramakrishnan , Uri Shaft, Compressing Relations and Indexes, Proceedings of the Fourteenth International Conference on Data Engineering, p.370-379, February 23-27, 1998
• 9: M. M. Halldórsson. "Approximations of Weighted Independent Set and Hereditary Subset Problems". Journal of Graph Algorithms and Applications, 4(1):1-16, 2000.
• 10: Dorit S. Hochbaum, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 11: H. V. Jagadish , J. Madar , Raymond T. Ng, Semantic Compression and Pattern Extraction with Fascicles, Proceedings of the 25th International Conference on Very Large Data Bases, p.186-198, September 07-10, 1999
• 12: Yasuhiko Morimoto , Hiromu Ishii , Shinichi Morishita, Efficient Construction of Regression Trees with Range and Region Splitting, Proceedings of the 23rd International Conference on Very Large Data Bases, p.166-175, August 25-29, 1997
• 13: Wee Keong Ng , Chinya V. Ravishankar, Block-Oriented Compression Techniques for Large Statistical Databases, IEEE Transactions on Knowledge and Data Engineering, v.9 n.2, p.314-328, March 1997 [doi>10.1109/69.591455]
• 14: Judea Pearl, Probabilistic reasoning in intelligent systems: networks of plausible inference, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 15: Judea Pearl, Causality: models, reasoning, and inference, Cambridge University Press, New York, NY, 2000
• 16: J. R. Quinlan , R. L. Rivest, Inferring decision trees using the minimum description length principle, Information and Computation, v.80 n.3, p.227-248, Mar. 1989 [doi>10.1016/0890-5401(89)90010-2]
• 17: Rajeev Rastogi , Kyuseok Shim, PUBLIC: A Decision Tree Classifier that Integrates Building and Pruning, Proceedings of the 24rd International Conference on Very Large Data Bases, p.404-415, August 24-27, 1998
• 18: John C. Shafer , Rakesh Agrawal , Manish Mehta, SPRINT: A Scalable Parallel Classifier for Data Mining, Proceedings of the 22th International Conference on Very Large Data Bases, p.544-555, September 03-06, 1996
• 19: William Stallings, SNMP,SNMPV2,Snmpv3,and RMON 1 and 2, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1998
• 20: J. Ziv and A. Lempel. "A Universal Algorithm for Sequential Data Compression". IEEE Trans. on Information Theory, 23(3), 1977.
• 21: J. Ziv and A. Lempel. "Compression of Individual Sequences via Variable-rate Coding". IEEE Trans. on Information Theory, 24(5), 1978.