Opportunistic data structures with applications

By Paolo Ferragina, Giovanni Manzini. 2000

1,308 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computer Networks and Communications, Molecular Biology, Natural Language Processing, Algorithms & Complexity

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Molecular Biology

In Natural Language Processing

In Algorithms & Complexity

Citations in the corpus

Re2G: Retrieve, Rerank, Generate (2022, methodology): “The neural retrieval generator is based on BART and constrained to generate ngrams that appear in the corpus with an FM-Index [Ferragina and Manzini, 2000].”
Autoregressive Search Engines: Generating Substrings as Document Identifiers (2022, methodology): “…we introduce S earch E ngines with A utoregressive L Ms (SEAL), a retrieval solution that combines an autoregressive model, i.e. , BART (Lewis et al., 2019), with a compressed full-text substring index, i.e. , the FM-Index (Ferragina and Manzini, 2000) — see Figure 1 for an high-level overview.”
Adaptive seeds tame genomic sequence comparison. (2011, background): “An FM-index (Ferragina and Manzini 2000) would use minimal memory, although its theoretical run time is inferior to that of the suffix tree (since it lacks suffix links).”
From RNA-seq reads to differential expression results (2010, neutral): “A detailed explanation of these techniques is beyond the scope of this review, but can be found in [23,26-30].”
Indexing compressed text (2005, methodology): “However, the compressed index described in Section 3 has been implemented and extensively tested in Ferragina and Manzini [2001]. The experiments show that our index, which also encapsulates the input text, takes roughly the same space used by the traditional compressors gzip and bzip2 that store th”
Exploring single-sample SNP and INDEL calling with whole-genome de novo assembly (2012, background): “lso deﬁne the accumulative count array C(a) as the number of symbols in T that are lexicographically smaller than a, and the occurrence array O(a,i) as the occurrence of symbols a in B[0,i]. FM-index(Ferragina and Manzini, 2000) is a compressed representation of the BWT B, the occurrence array O(a,i”
Searching for SNPs with cloud computing (2009, methodology): “For alignment, Crossbow uses Bowtie [17], which employs a Burrows-Wheeler index [25] based on the full-text minute-space (FM) index [26] to enable fast and memory-efficient alignment of short reads to mammalian genomes.”
Fast Identification and Removal of Sequence Contamination from Genomic and Metagenomic Datasets (2011, methodology): “The FM-index proposed by Ferragina and Manzini [36] was originally designed as a compressed data structure and is used by alignment programs to improve the memory usage (typically 0.”
Benchmarking Metagenomics Tools for Taxonomic Classification. (2019, background): “Among the DNA-to-protein classifiers, MMseqs2 required extremely high amounts of memory and computational time, while Kaiju was fairly quick due to the use of an FM-index.”
Compressed suffix arrays and suffix trees with applications to text indexing and string matching (extended abstract) (2000, methodology): “Manzini [29, 30] have devised the Fast Minute index (FM-index), based upon the”
Bridging the Gap Between Indexing and Retrieval for Differentiable Search Index with Query Generation (2022, methodology): “At inference time, SEAL directly generates ngrams which can be used to score and retrieve documents stored in an FM-index [12].”
A four-stage algorithm for updating a Burrows-Wheeler transform (2009, methodology): “This function LF , which permits to compute the position of a cyclic shift T [i] from the position of the cyclic shift T , is defined [7] as LF (p) = CT [L[p]] + rankL[p](L, p)− 1.”
Transcript-level expression analysis of RNA-seq experiments with HISAT, StringTie, and Ballgown (2016, methodology): “Through the use of a special indexing scheme called the Ferragina–Manzini (FM) index 29 , these programs can search a genome extremely rapidly, yielding alignment speeds measured in millions of reads per hour.”
High-order entropy-compressed text indexes (2003, methodology): “Indexing the Associated Press file with the FM-index would require roughly 1 gigabyte according to the experiments in [3].”
Replacing suffix trees with enhanced suffix arrays (2004, background): “The most notable ones are the compressed suffix array introduced by Grossi and Vitter [14] and the so-called opportunistic data structure devised by Ferragina and Manzini [10].”
High speed BLASTN: an accelerated MegaBLAST search tool (2015, methodology): “Otherwise, we must iteratively call the Last-toFirst column mapping (LF-mapping) (lines 7-8, see (30) for details) until we reach the position x that is divisible by r (line 6), and get SA[k] = SA[x] + iter (line 11), where iter is the number of iterations.”
Linear work suffix array construction (2006, background): “An even more space-efficient approach is to construct compressed indexes [21, 27, 42, 31, 32].”
Mapping single molecule sequencing reads using basic local alignment with successive refinement (BLASR): application and theory (2012, methodology): “The COUNTLCP operation is about 1.5× faster using a suffix array than a BWT-FM index, in our tests searching the human genome and limiting the number of times an LCP occurs to 10,000; however, the space usage for the index on a human genome is 12.8 GB with a suffix array, vs. 4.8 GB in our implement”