Document retrieval hacks

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


Given a collection of strings, document listing refers to the problem of finding all the strings (or documents) where a given query string (or pattern) appears. Index data structures that support efficient document listing for string collections have been the focus of intense research in the last decade, with dozens of papers published describing exotic and elegant compressed data structures. The problem is now quite well understood in theory and many of the solutions have been implemented and evaluated experimentally. A particular recent focus has been on highly repetitive document collections, which have become prevalent in many areas (such as version control systems and genomics - to name just two very different sources). The aim of this paper is to describe simple and efficient document listing algorithms that can be used in combination with more sophisticated techniques, or as baselines against which the performance of new document listing indexes can be measured. Our approaches are based on simple combinations of scanning and hashing, which we show to combine very well with dictionary compression to achieve small space usage. Our experiments show these methods to be often much faster and less space consuming than the best specialized indexes for the problem.

Original languageEnglish
Title of host publication19th International Symposium on Experimental Algorithms, SEA 2021
EditorsDavid Coudert, Emanuele Natale
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Publication date1 Jun 2021
Article number12
ISBN (Electronic)9783959771856
Publication statusPublished - 1 Jun 2021
MoE publication typeA4 Article in conference proceedings
EventInternational Symposium on Experimental Algorithms - Virtual, Nice, France
Duration: 7 Jun 20219 Jun 2021
Conference number: 19

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
ISSN (Print)1868-8969

Fields of Science

  • Document listing
  • Document retrieval
  • Pattern matching
  • Repetitive text collections
  • String processing
  • Succinct data structures
  • 113 Computer and information sciences

Cite this