| Skip to main content | Skip to navigation |

Register Now!

Compressing and Searching XML Data Via Two Zips

  • P. Ferragina, Dip. Informatica, Univ. Pisa, Italy
  • F. Luccio, Dip. Informatica, Univ. Pisa, Italy
  • G. Manzini, Dip. Informatica, Univ. Piemonte Orientale, Italy
  • S. Muthukrishnan, Dept Computer Science, Rutgers Univ., USA

Full text:

Presentation Slides:

Track: Industrial Practice and Experience

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.

Citation

Ferragina, P., Luccio, F., Manzini, G., and Muthukrishnan, S. 2006. Compressing and searching XML data via two zips. In Proceedings of the 15th International Conference on World Wide Web (Edinburgh, Scotland, May 23 - 26, 2006). WWW '06. ACM Press, New York, NY, 751-760.
DOI= http://doi.acm.org/10.1145/1135777.1135891

Organised by

ECS Logo

in association with

BCS Logo ACM Logo

Platinum Sponsors

Sponsor of The CIO Dinner


Become a sponsor or exhibitor
Valid XHTML 1.0! IFIP logo WWW Conference Committee logo Web Consortium logo Valid CSS!