XMill: an efficient compressor for XML data

ABSTRACT

We describe a tool for compressing XML data, with applications in data exchange and archiving, which usually achieves about twice the compression ratio of gzip at roughly the same speed. The compressor, called XMill, incorporates and combines existing compressors in order to apply them to heterogeneous XML data: it uses zlib, the library function for gzip, a collection of datatype specific compressors for simple data types, and, possibly, user defined compressors for application specific data types.

REFERENCES

• 1: D. Belanger and K. Church. Data flows with examples from telecommunications. In Proceedings of 1999 Workshop on Databases in Telecommunication, Edinburgh, UK, September 1999.
• 2: Timothy C. Bell , John G. Cleary , Ian H. Witten, Text compression, Prentice-Hall, Inc., Upper Saddle River, NJ, 1990
• 3: M. Burrows and D. J. Wheeler. A block-sorting lossless data compression algorithm. Technical report, Digital Equipment Corporation, May 1994.
• 4: Clark and S. DeRose. XML path language (XPath), version 1.0. W3C Working Draft, August 1999. Available as http ://www. w3. org/TR/xpath.
• 5: Roy Goldman , Jennifer Widom, DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases, Proceedings of the 23rd International Conference on Very Large Data Bases, p.436-445, August 25-29, 1997
• 6: 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
• 7: Stéphane Grumbach , Fariza Tahi, A new challenge for compression algorithms: genetic sequences, Information Processing and Management: an International Journal, v.30 n.6, p.875-886, 1994 [doi>10.1016/0306-4573(94)90014-0]
• 8: D. G. Higgins, R. Fuchs, P. J. Stoehr, and G. N. Cameron. The EMBL data library. Nucleic Acids Research, 20:2071- 2074, 1992.
• 9: John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 10: Balakrishna R. Iyer , David Wilhite, Data Compression Support in Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.695-704, September 12-15, 1994
• 11: Hartmut Liefke , Dan Suciu, An extensible compressor for XML data, ACM SIGMOD Record, v.29 n.1, p.57-62, March 2000 [doi>10.1145/344788.344815]
• 12: H. Liefke and D. Suciu. XMill: An efficient compressor for XML data. Technical Report MS-CIS-98-06, Department of Computer and Information Science, University of Pennsylvania, Philadelphia, PA 19104, October 1999.
• 13: Mitchell P. Marcus , Mary Ann Marcinkiewicz , Beatrice Santorini, Building a large annotated corpus of English: the penn treebank, Computational Linguistics, v.19 n.2, June 1993
• 14: S. Nestorov, S. Abiteboul, and R. Motwani. Inferring structure in semistructured data. In Proceedings of the Workshop on Management of Semi-structured Data, 1997. Available from http ://www. research, att. com/~ suc iu/workshop-papers, html.
• 15: 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]
• 16: Mark A. Roth , Scott J. Van Horn, Database compression, ACM SIGMOD Record, v.22 n.3, p.31-39, Sept. 1993 [doi>10.1145/163090.163096]
• 17: David Salomon, Data compression: the complete reference, Springer-Verlag New York, Inc., New York, NY, 1997
• 18: Neil J. A. Sloane , Aaron D. Wyner , Claude E. Shannon, Claude Elwood Shannon: collected papers, IEEE Press, Piscataway, NJ, 1993
• 19: H.S. Thompson, D. Beech, M. Maloney, and N. Mendelsohn. XML schema part 1: Structures. 1/113C Working Draft, September 1999. Available as http://www, w3. org/TR/xmls chema-I.
• 20: J. Ziv and A. Lempel. A universal algorithm for sequential data compression. IEEE Transactions on Information Theory, 23(3):337-343, 1977.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL

General Terms:
Algorithms, Design, Experimentation