Entry pairing in inverted file

T.L. Hoang, R. Perego, T.M.Q. Nguyen, F. Silvestri

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    7 Citations (Scopus)


    This paper proposes to exploit content and usage information to rearrange an inverted index for a full-text IR system. The idea is to merge the entries of two frequently co-occurring terms, either in the collection or in the answered queries, to form a single, paired, entry. Since postings common to paired terms are not replicated, the resulting index is more compact. In addition, queries containing terms that have been paired are answered faster since we can exploit the pre-computed posting intersection. In order to choose which terms have to be paired, we formulate the term pairing problem as a Maximum-Weight Matching Graph problem, and we evaluate in our scenario efficiency and efficacy of both an exact and a heuristic solution. We apply our technique: (i) to compact a compressed inverted file built on an actual Web collection of documents, and (ii ) to increase capacity of an in-memory posting list. Experiments showed that in the first case our approach can improve the compression ratio of up to 7.7%, while we measured a saving from 12% up to 18% in the size of the posting cache.
    Original languageEnglish
    Title of host publicationProceedings of the 10th International Conference on Web Information Systems Engineering (WISE 2009), 5-7 October 2009, Poznan, Poland
    EditorsG. Vossen, D.E. Long, J.X. Lu
    Place of PublicationBerlin
    ISBN (Print)978-3-642-04408-3
    Publication statusPublished - 2009

    Publication series

    NameLecture Notes in Computer Science
    ISSN (Print)0302-9743


    Dive into the research topics of 'Entry pairing in inverted file'. Together they form a unique fingerprint.

    Cite this