Compressing and searching XML data via two zips

ABSTRACT

XML is fast becoming the standard format to store, exchange and publish over the web, and is getting embedded in applications. Two challenges in handling XML are its size (the XML representation of a document is significantly larger than its native state) and the complexity of its search (XML search involves path and content searches on labeled tree structures). We address the basic problems of compression, navigation and searching of XML documents. In particular, we adopt recently proposed theoretical algorithms [11] for succinct tree representations to design and implement a compressed index for XML, called XBZIPiNDEX, in which the XML document is maintained in a highly compressed format, and both navigation and searching can be done uncompressing only a tiny fraction of the data. This solution relies on compressing and indexing two arrays derived from the XML data. With detailed experiments we compare this with other compressed XML indexing and searching engines to show that XBZIPiNDEX has compression ratio up to 35% better than the ones achievable by those other tools, and its time performance on some path and content search operations is order of magnitudes faster: few milliseconds over hundreds of MBs of XML files versus tens of seconds, on standard XML data sources.

REFERENCES

• 1: http://xml.coverpages.org/xml.html.
• 2: Joaquín Adiego , Gonzalo Navarro , Pablo de la Fuente, Lempel-Ziv Compression of Structured Text, Proceedings of the Conference on Data Compression, p.112, March 23-25, 2004
• 3: Joaquín Adiego , Pablo de la Fuente , Gonzalo Navarro, Merging Prediction by Partial Matching with Structural Contexts Model, Proceedings of the Conference on Data Compression, p.522, March 23-25, 2004
• 4: A. Arion, A. Bonifati, G. Costa, S. D'Aguanno, I. Manolescu, and A. Pugliese. XQueC: pushing queries to compressed XML data. In VLDB, 2003.
• 5: David Benoit , Erik D. Demaine , J. Ian Munro , Rajeev Raman , Venkatesh Raman , S. Srinivasa Rao, Representing Trees of Higher Degree, Algorithmica, v.43 n.4, p.275-292, December 2005 [doi>10.1007/s00453-004-1146-6]
• 6: Barbara Catania , Anna Maddalena , Athena Vakali, XML Document Indexes: A Classification, IEEE Internet Computing, v.9 n.5, p.64-71, September 2005 [doi>10.1109/MIC.2005.115]
• 7: Ting Chen , Jiaheng Lu , Tok Wang Ling, On boosting holism in XML twig pattern matching using structural indexing techniques, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066209]
• 8: James Cheney, Compressing XML with Multiplexed Hierarchical PPM Models, Proceedings of the Data Compression Conference (DCC '01), p.163, March 27-29, 2001
• 9: J. Cheney. An empirical evaluation of simple DTD-conscious compression techniques. In WebDB, 2005.
• 10: J. Cheng and W. Ng. XQzip: Querying compressed XML using structural indexing. In International Conference on Extending Database Technology, pages 219--236, 2004.
• 11: Paolo Ferragina , Fabrizio Luccio , Giovanni Manzini , S. Muthukrishnan, Structuring labeled trees for optimal succinctness, and beyond, Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, p.184-196, October 23-25, 2005 [doi>10.1109/SFCS.2005.69]
• 12: An experimental study of a compressed index, Information Sciences: an International Journal, v.135 n.1-2, p.13-28, June, 2001 [doi>10.1016/S0020-0255(01)00098-6 ]
• 13: Paolo Ferragina , Giovanni Manzini, Indexing compressed text, Journal of the ACM (JACM), v.52 n.4, p.552-581, July 2005 [doi>10.1145/1082036.1082039]
• 14: Richard F. Geary , Rajeev Raman , Venkatesh Raman, Succinct ordinal trees with level-ancestor queries, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 15: David Geer, Will Binary XML Speed Network Traffic?, Computer, v.38 n.4, p.16-18, April 2005 [doi>10.1109/MC.2005.143]
• 16: 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
• 17: Alexander Golynski , J. Ian Munro , S. Srinivasa Rao, Rank/select operations on large alphabets: a tool for text indexing, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.368-373, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109599]
• 18: Raghav Kaushik , Rajasekar Krishnamurthy , Jeffrey F. Naughton , Raghu Ramakrishnan, On the integration of structure indexes and inverted lists, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007656]
• 19: Raghav Kaushik , Rajasekar Krishnamurthy , Jeffrey F. Naughton , Raghu Ramakrishnan, On the integration of structure indexes and inverted lists, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007656]
• 20: W. Y. Lam, W. Ng, P. T. Wood, and M. Levene. XCQ: XML compression and querying system. In WWW, 2003.
• 21: Hartmut Liefke , Dan Suciu, XMill: an efficient compressor for XML data, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.153-164, May 15-18, 2000, Dallas, Texas, United States
• 22: Tova Milo , Dan Suciu, Index Structures for Path Expressions, Proceeding of the 7th International Conference on Database Theory, p.277-295, January 10-12, 1999
• 23: Jun-Ki Min , Myung-Jae Park , Chin-Wan Chung, XPRESS: a queriable compression for XML data, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872775]
• 24: Edleno Silva de Moura , Gonzalo Navarro , Nivio Ziviani , Ricardo Baeza-Yates, Fast and flexible word searching on compressed text, ACM Transactions on Information Systems (TOIS), v.18 n.2, p.113-139, April 2000 [doi>10.1145/348751.348754]
• 25: Praveen Rao , Bongki Moon, PRIX: Indexing And Querying XML Using Prüfer Sequences, Proceedings of the 20th International Conference on Data Engineering, p.288, March 30-April 02, 2004
• 26: Dmitry Shkarin, PPM: One Step to Practicality, Proceedings of the Data Compression Conference (DCC '02), p.202, April 02-04, 2002
• 27: XGRIND: A Query-Friendly XML Compressor, Proceedings of the 18th International Conference on Data Engineering, p.225, February 26-March 01, 2002
• 28: Haixun Wang , Sanghyun Park , Wei Fan , Philip S. Yu, ViST: a dynamic index method for querying XML data by tree structures, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872774]
• 29: Wei Wang , Haifeng Jiang , Hongzhi Wang , Xuemin Lin , Hongjun Lu , Jianzhong Li, Efficient processing of XML path queries using the disk-based F&B Index, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway

INDEX TERMS

Primary Classification:
  E. Data
  E.1 DATA STRUCTURES

Additional Classification:
  E. Data
  E.4 CODING AND INFORMATION THEORY
      Subjects: Data compaction and compression

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.0 General

General Terms:
Algorithms, Experimentation

Keywords:
XML compression and indexing, labeled trees