Spaces, Trees and Colors: The Algorithmic Landscape of Document Retrieval on Sequences
This is an incremental survey that benefits researchers in fields like bioinformatics and data mining by summarizing algorithmic advances for document retrieval on diverse sequences.
The survey addresses the limitation of current document retrieval technology, which fails to handle non-natural language sequences like East Asian languages, by reviewing recent research that extends techniques to broader sequence collections, uncovering algorithmic relations with fundamental problems in trees and strings.
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 indices are the preferred solution. As successful as this paradigm has been, it fails to properly handle some 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 bioinformatics, data and Web mining, chemoinformatics, software engineering, multimedia information retrieval, and many others. 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 others.