Document retrieval on repetitive string collections

Show full item record



Permalink

http://hdl.handle.net/10138/312492

Citation

Gagie , T , Hartikainen , A , Karhu , K , Kärkkäinen , J , Navarro , G , Puglisi , S J & Sirén , J 2017 , ' Document retrieval on repetitive string collections ' , Information Retrieval Journal , vol. 20 , no. 3 , pp. 253-291 . https://doi.org/10.1007/s10791-017-9297-7

Title: Document retrieval on repetitive string collections
Author: Gagie, Travis; Hartikainen, Aleksi; Karhu, Kalle; Kärkkäinen, Juha; Navarro, Gonzalo; Puglisi, Simon J.; Sirén, Jouni
Contributor organization: Department of Computer Science
Practical Algorithms and Data Structures on Strings research group / Juha Kärkkäinen
Finnish Centre of Excellence in Algorithmic Data Analysis Research (Algodan)
Helsinki Institute for Information Technology
Bioinformatics
Genome-scale Algorithmics research group / Veli Mäkinen
Algorithmic Bioinformatics
Date: 2017-06
Language: eng
Number of pages: 39
Belongs to series: Information Retrieval Journal
ISSN: 1386-4564
DOI: https://doi.org/10.1007/s10791-017-9297-7
URI: http://hdl.handle.net/10138/312492
Abstract: Most of the fastest-growing string collections today are repetitive, that is, most of the constituent documents are similar to many others. As these collections keep growing, a key approach to handling them is to exploit their repetitiveness, which can reduce their space usage by orders of magnitude. We study the problem of indexing repetitive string collections in order to perform efficient document retrieval operations on them. Document retrieval problems are routinely solved by search engines on large natural language collections, but the techniques are less developed on generic string collections. The case of repetitive string collections is even less understood, and there are very few existing solutions. We develop two novel ideas, interleaved LCPs and precomputed document lists, that yield highly compressed indexes solving the problem of document listing (find all the documents where a string appears), top-k document retrieval (find the k documents where a string appears most often), and document counting (count the number of documents where a string appears). We also show that a classical data structure supporting the latter query becomes highly compressible on repetitive data. Finally, we show how the tools we developed can be combined to solve ranked conjunctive and disjunctive multi-term queries under the simple model of relevance. We thoroughly evaluate the resulting techniques in various real-life repetitiveness scenarios, and recommend the best choices for each case.
Subject: Repetitive string collections
Document retrieval on strings
Suffix trees and arrays
INFORMATION-RETRIEVAL
EFFICIENT ALGORITHMS
SUFFIX ARRAYS
TEXT INDEXES
SEQUENCES
113 Computer and information sciences
Peer reviewed: Yes
Rights: cc_by
Usage restriction: openAccess
Self-archived version: publishedVersion


Files in this item

Total number of downloads: Loading...

Files Size Format View
Gagie2017_Artic ... RetrievalOnRepetitiveS.pdf 817.8Kb PDF View/Open

This item appears in the following Collection(s)

Show full item record