Spaces, trees, and colors: the algorithmic landscape of document retrieval on sequences
From MaRDI portal
(Redirected from Publication:5176183)
Abstract: 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.
Recommendations
Cites work
- A Generalized Suffix Tree and Its (Un)Expected Asymptotic Behaviors
- A Space-Economical Suffix Tree Construction Algorithm
- A unifying look at data structures
- Algorithms on Strings, Trees and Sequences
- Alphabet-independent compressed text indexing
- An analysis of the Burrows-Wheeler transform
- An experimental investigation of set intersection algorithms for text searching
- Cell probe lower bounds and approximations for range mode
- Colored range queries and document retrieval
- Compressed Text Indexes with Fast Locate
- Compressed text indexes, from theory to practice
- Compression, indexing, and retrieval for massive string data
- Constructing suffix arrays in linear time
- Design and implementation of an efficient priority queue
- Document listing for queries with excluded pattern
- Efficient fully-compressed sequence representations
- Efficient index for retrieving top-\(k\) most frequent documents
- Fast Algorithms for Finding Nearest Common Ancestors
- Fast set intersection and two-patterns matching
- Fully-functional succinct trees
- Further Results on Generalized Intersection Searching Problems: Counting, Reporting, and Dynamization
- GENERALIZED INTERSECTION SEARCHING PROBLEMS
- scientific article; zbMATH DE number 3887059 (Why is no real title available?)
- scientific article; zbMATH DE number 3913711 (Why is no real title available?)
- scientific article; zbMATH DE number 3738962 (Why is no real title available?)
- scientific article; zbMATH DE number 3511563 (Why is no real title available?)
- scientific article; zbMATH DE number 2038723 (Why is no real title available?)
- scientific article; zbMATH DE number 2079421 (Why is no real title available?)
- scientific article; zbMATH DE number 1512678 (Why is no real title available?)
- scientific article; zbMATH DE number 2119724 (Why is no real title available?)
- scientific article; zbMATH DE number 756768 (Why is no real title available?)
- Improved compressed indexes for full-text document retrieval
- Information retrieval. Implementing and evaluating search engines.
- Jewels of Stringology
- Linear work suffix array construction
- Linear-space data structures for range mode query in arrays
- Mining query logs: turning search usage data into knowledge
- New algorithms on wavelet trees and applications to information retrieval
- New lower and upper bounds for representing sequences
- On Finding Lowest Common Ancestors: Simplification and Parallelization
- On-line construction of suffix trees
- Optimal trade-offs for succinct string indexes
- Orthogonal range searching for text indexing
- Range selection and median: tight cell probe lower bounds and adaptive data structures
- Rank/select operations on large alphabets
- Recursive Star-Tree Parallel Data Structure
- Space efficient linear time construction of suffix arrays
- Space-efficient data-analysis queries on grids
- Space-Efficient Framework for Top-k String Retrieval Problems
- Space-efficient preprocessing schemes for range minimum queries on static arrays
- Succinct data structures for flexible text retrieval systems
- Succinct Indexable Dictionaries with Applications to Encoding k-ary Trees, Prefix Sums and Multisets
- Succinct Orthogonal Range Search Structures on a Grid with Applications to Text Indexing
- Suffix Arrays: A New Method for On-Line String Searches
- Top-\(K\) color queries for document retrieval
- Top-k document retrieval in compact space and near-optimal time
- Top-k document retrieval in external memory
- Top-k document retrieval in optimal space
- Top-\(k\) ranked document search in general text databases
- Towards an optimal space-and-query-time index for top-k document retrieval
- Towards optimal range medians
- Two-dimensional substring indexing.
- Wavelet trees for all
- Web data mining. Exploring hyperlinks, contents, and usage data.
Cited in
(35)- Space-efficient indexes for forbidden extension queries
- \(xkcd\)-repeats: a new taxonomy of repeats defined by their context diversity
- Ranked document retrieval for multiple patterns
- New space/time tradeoffs for top-\(k\) document retrieval on sequences
- In-place initializable arrays
- String indexing for top-\(k\) close consecutive occurrences
- Efficient computation of spatial queries over points stored in \(k^2\)-tree compact data structures
- Lempel-Ziv compressed structures for document retrieval
- Ranked document selection
- On hardness of several string indexing problems
- Bottom-\(k\) document retrieval
- Top-k term-proximity in succinct space
- Grammar compressed sequences with rank/select support
- Document listing on repetitive collections with guaranteed performance
- Gapped indexing for consecutive occurrences
- Document retrieval with one wildcard
- Ranked document retrieval with forbidden pattern
- Encodings of range maximum-sum segment queries and applications
- Compact indexes for flexible top-k
- Time-optimal top-k document retrieval
- The longest common substring problem
- Space-efficient frameworks for top-k string retrieval
- Optimal encodings for range top-\(k\), selection, and min-max
- Access, rank, and select in grammar-compressed strings
- scientific article; zbMATH DE number 2119724 (Why is no real title available?)
- Extra space during initialization of succinct data structures and dynamical initializable arrays
- Structural Pattern Matching - Succinctly.
- On-the-fly array initialization in less space
- Inducing enhanced suffix arrays for string collections
- Practical compact indexes for top-k document retrieval
- Ranked Document Retrieval in External Memory
- Space-time trade-offs for the LCP array of Wheeler DFAs
- String indexing for top-\(k\) close consecutive occurrences
- Tight bounds for monotone minimal perfect hashing
- Counting on general run-length grammars
This page was built for publication: Spaces, trees, and colors: the algorithmic landscape of document retrieval on sequences
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5176183)
