Compressing and searching XML data via two zips

P. Ferragina, F. Luccio, G. Manzini, S. Muthukrishnan

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

    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 signifi-cantly 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 XBzipIn-dex, 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.

    Original languageEnglish (US)
    Title of host publicationProceedings of the 15th International Conference on World Wide Web
    Pages751-760
    Number of pages10
    DOIs
    StatePublished - 2006
    Event15th International Conference on World Wide Web - Edinburgh, Scotland, United Kingdom
    Duration: May 23 2006May 26 2006

    Publication series

    NameProceedings of the 15th International Conference on World Wide Web

    Other

    Other15th International Conference on World Wide Web
    CountryUnited Kingdom
    CityEdinburgh, Scotland
    Period5/23/065/26/06

    Keywords

    • Labeled trees
    • XML compression and indexing

    ASJC Scopus subject areas

    • Computer Networks and Communications
    • Software

    Fingerprint Dive into the research topics of 'Compressing and searching XML data via two zips'. Together they form a unique fingerprint.

    Cite this