Inverted index compression and query processing with optimized document ordering

Hao Yan, Shuai Ding, Torsten Suel

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

    Abstract

    Web search engines use highly optimized compression schemes to decrease inverted index size and improve query through-put, and many index compression techniques have been studied in the literature. One approach taken by several recent studies [7, 23, 25, 6, 24] first performs a renumbering of the document IDs in the collection that groups similar documents together, and then applies standard compression techniques. It is known that this can significantly improve index compression compared to a random document ordering. We study index compression and query processing techniques for such reordered indexes. Previous work has focused on determining the best possible ordering of documents. In contrast, we assume that such an ordering is already given, and focus on how to optimize compression methods and query processing for this case. We perform an extensive study of compression techniques for document IDs and present new optimizations of existing techniques which can achieve significant improvement in both compression and decompression performances. We also propose and evaluate techniques for compressing frequency values for this case. Finally, we study the effect of this approach on query processing performance. Our experiments show very significant improvements in index size and query processing speed on the TREC GOV2 collection of 25.2 million web pages. Copyright is held by the International World Wide Web Conference Committee (IW3C2).

    Original languageEnglish (US)
    Title of host publicationWWW'09 - Proceedings of the 18th International World Wide Web Conference
    Pages401-410
    Number of pages10
    DOIs
    StatePublished - 2009
    Event18th International World Wide Web Conference, WWW 2009 - Madrid, Spain
    Duration: Apr 20 2009Apr 24 2009

    Publication series

    NameWWW'09 - Proceedings of the 18th International World Wide Web Conference

    Other

    Other18th International World Wide Web Conference, WWW 2009
    Country/TerritorySpain
    CityMadrid
    Period4/20/094/24/09

    Keywords

    • Document ordering
    • IR query processing
    • Index compression
    • Inverted index
    • Search engines

    ASJC Scopus subject areas

    • Computer Networks and Communications

    Fingerprint

    Dive into the research topics of 'Inverted index compression and query processing with optimized document ordering'. Together they form a unique fingerprint.

    Cite this