High-order entropy-compressed text indexes
By Roberto Grossi, Ankur Gupta, Jeffrey Scott Vitter. 2003
841 citations recorded by the source corpus.
Subfields: Information Retrieval & Search
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Information Retrieval & Search
- Sebastian Riedel
- Fabio Petroni
- Wen-tau Yih
- Eric Sadit Tellez
- Patrick Lewis
- Edgar Chávez
- Mario Graff
- Gonzalo Navarro
Citations in the corpus
- Autoregressive Search Engines: Generating Substrings as Document Identifiers (2022, background): “…sorted, so it can be represented with one count for each alphabet symbol; L , the string’s BWT, will be stored in a data structure known as the Wavelet Tree (Grossi et al., 2003), which allows efficient rank-select-access queries, while exploiting the compressibility induced by the transformation.”
- Practical Entropy-Compressed Rank/Select Dictionary (2006, methodology): “Various succinct representation techniques have been developed to represent data structures such as ordered sets [25, 19, 20, 21], ordinal trees [1, 26, 5, 6, 13, 18, 23], strings [4, 9, 10, 22, 23, 24], functions [17], and labeled trees [1, 3].”
- N-gram IDF: A Global Term Weighting Scheme Based on Information Distance (2015, methodology): “Second, we utilize wavelet tree [17] for counting the document frequency of the conjunction of words.”
- The Case for Learned Index Structures (2017, background): “Succinct Data Structures: There exists an interesting connection between learned indexes and succinct data structures, especially rank-select dictionaries such as wavelet trees [38, 39].”
- Indexing compressed text (2005, methodology): “2002], wavelet trees [Grossi et al. 2003] and compression boosting [Ferragina et al.”
- Near neighbor searching with K nearest references (2015, background): “There are several proposals in the literature [26,25, 20,7,8] that offer different space/time tradeoffs for representing an IoS.”
- Parallel Lightweight Wavelet Tree, Suffix Array and FM-Index Construction (2016, background): “Wavelet trees (WT) generalize this to larger alphabets [8].”