A Space-Efficient Indexing Algorithm for Boolean Query Processing

Jianbin Qin, Chuan Xiao, Wei Wang, Xuemin Lin

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

Abstract / Description of output

Inverted indexes are the fundamental index for information retrieval systems. Due to the correlation between terms, inverted lists in the index may have substantial overlap and hence redundancy. In this paper, we propose a new approach that reduces the size of inverted lists while retaining time-efficiency. Our solution is based on merging inverted lists that bear high overlap to each other and manage their content in the resulting condensed index. An efficient algorithm is designed to discover heavily-overlapped inverted lists and construct the condensed index for a given dataset. We demonstrate that our algorithm delivers considerable space saving while incurring little query performance overhead.
Original languageEnglish
Title of host publicationWeb Information Systems Engineering - WISE 2012 - 13th International Conference, Paphos, Cyprus, November 28-30, 2012. Proceedings
Place of PublicationPaphos, Cyprus
PublisherSpringer Berlin Heidelberg
Number of pages7
ISBN (Electronic)978-3-642-35063-4
ISBN (Print)978-3-642-35062-7
Publication statusPublished - 2012
Event13th International Conference on Web Information System Engineering - Paphos, Cyprus
Duration: 28 Nov 201230 Nov 2012


Conference13th International Conference on Web Information System Engineering
Abbreviated titleWISE 2012
Internet address


Dive into the research topics of 'A Space-Efficient Indexing Algorithm for Boolean Query Processing'. Together they form a unique fingerprint.

Cite this