Document retrieval on repetitive string collections

Area of Science:

• Computer Science
• Information Retrieval
• Data Compression

Background:

• Fast-growing string collections are often repetitive, with many similar documents.
• Existing document retrieval techniques are less developed for generic and repetitive string collections.
• Exploiting repetitiveness can drastically reduce space usage in large collections.

Purpose of the Study:

• To develop efficient indexing methods for repetitive string collections.
• To enable fast document retrieval operations on these compressed collections.
• To address the challenges posed by the increasing size and repetitiveness of data.

Main Methods:

• Development of two novel techniques: interleaved Longest Common Prefixes (LCPs) and precomputed document lists.
• Creation of highly compressed indexes for document listing, top-k retrieval, and document counting.
• Adaptation of classical data structures for compressibility on repetitive data.

Main Results:

• Achieved highly compressed indexes for efficient document retrieval.
• Demonstrated the compressibility of classical data structures on repetitive data.
• Successfully combined developed tools to solve ranked multi-term queries.

Conclusions:

• Novel indexing techniques significantly improve space efficiency and retrieval performance for repetitive string collections.
• The developed methods provide effective solutions for document listing, top-k retrieval, and counting.
• The approach offers a robust framework for handling large, repetitive datasets in information retrieval.