Spaces, Trees, and Colors: The Algorithmic Landscape of Document Retrieval on Sequences

Navarro G.

Abstract

Document retrieval is one of the best-established information retrieval activities since the '60s, 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 retrieval 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.

Más información

Título según WOS: Spaces, Trees, and Colors: The Algorithmic Landscape of Document Retrieval on Sequences
Título según SCOPUS: Spaces, trees, and colors: The algorithmic landscape of document retrieval on sequences
Título de la Revista: ACM COMPUTING SURVEYS
Volumen: 46
Número: 4
Editorial: ASSOC COMPUTING MACHINERY
Fecha de publicación: 2014
Idioma: English
DOI:

10.1145/2535933

Notas: ISI, SCOPUS