Spaces, Trees and Colors: The Algorithmic Landscape of Document Retrieval on
Document retrieval is one of the best established information retrieval
activities since the sixties, pervading all search engines. Its aim is to
obtain, from a collection of text documents, those most relevant to a pattern
query. Current technology is mostly oriented to "natural language" text
collections, where inverted indexes are the preferred solution. As
successful as this paradigm has been, it fails to properly handle various
East Asian languages and other scenarios where the "natural language"
assumptions do not hold.
In this survey we cover the recent research in extending the document
techniques to a broader class of sequence collections, which has
applications in bioinformatics, data and Web mining, chemoinformatics,
software engineering, multimedia information retrieval, and many other fields.
We focus on the algorithmic aspects of the techniques, uncovering a rich world
of relations between document retrieval challenges and fundamental problems on
trees, strings, range queries, discrete geometry, and other areas.