Document Retrieval on Repetitive Collections
This work addresses a gap in experimental evaluation for document retrieval, providing insights for researchers and practitioners dealing with repetitive data collections, though it is incremental as it builds on existing methods.
The paper tackled the problem of determining which document retrieval methods outperform brute-force approaches and perform best based on collection characteristics, finding that established solutions are often beaten by brute-force alternatives and designing new methods with superior time/space trade-offs, especially on repetitive collections.
Document retrieval aims at finding the most important documents where a pattern appears in a collection of strings. Traditional pattern-matching techniques yield brute-force document retrieval solutions, which has motivated the research on tailored indexes that offer near-optimal performance. However, an experimental study establishing which alternatives are actually better than brute force, and which perform best depending on the collection characteristics, has not been carried out. In this paper we address this shortcoming by exploring the relationship between the nature of the underlying collection and the performance of current methods. Via extensive experiments we show that established solutions are often beaten in practice by brute-force alternatives. We also design new methods that offer superior time/space trade-offs, particularly on repetitive collections.