The DOI matches its Crossref record; 15 of the 15 references it cites were found in a registry or an index.
Opportunistic data structures with applications
Abstract
We address the issue of compressing and indexing data. We devise a data structure whose space occupancy is a function of the entropy of the underlying data set. We call the data structure opportunistic since its space occupancy is decreased when the input is compressible and this space reduction is achieved at no significant slowdown in the query performance. More precisely, its space occupancy is optimal in an information-content sense because text T[1,u] is stored using O(H/sub k/(T))+o(1) bits per input symbol in the worst case, where H/sub k/(T) is the kth order empirical entropy of T (the bound holds for any fixed k). Given an arbitrary string P[1,p], the opportunistic data structure allows to search for the occurrences of P in T in O(p+occlog/sup /spl epsiv//u) time (for any fixed /spl epsiv/>0). If data are uncompressible we achieve the best space bound currently known (Grossi and Vitter, 2000); on compressible data our solution improves the succinct suffix array of (Grossi and Vitter, 2000) and the classical suffix tree and suffix array data structures either in space or in query time or both. We also study our opportunistic data structure in a dynamic setting and devise a variant achieving effective search and update time bounds. Finally, we show how to plug our opportunistic data structure into the Glimpse tool (Manber and Wu, 1994). The result is an indexing tool which achieves sublinear space and sublinear query time complexity.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
The Art of Computer Programming
Whitesides, G. E. (1970) · Nuclear Science and Engineering · doi:10.13182/nse70-a19705 · Cited by 6,008
A Block-sorting Lossless Data Compression Algorithm
Burrows, M. T., & Wheeler, D. J. (1994) · Cited by 2,333
Suffix Arrays: A New Method for On-Line String Searches
Manber, U., & Myers, G. (1993) · SIAM Journal on Computing · doi:10.1137/0222058 · Cited by 1,915
Knuth, D. E. (1973) · Cumulative Index of Computer Aided Architectural Design · Cited by 1,719
A Space-Economical Suffix Tree Construction Algorithm
McCreight, E. M. (1976) · Journal of the ACM · doi:10.1145/321941.321946 · Cited by 1,511
A locally adaptive data compression scheme
Bentley, J. L., Sleator, D. D., Tarjan, R. E., & Wei, V. K. (1986) · Communications of the ACM · doi:10.1145/5684.5688 · Cited by 523
Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
Grossi, R., & Vitter, J. S. (2005) · SIAM Journal on Computing · doi:10.1137/s0097539702402354 · Cited by 431
An analysis of the Burrows—Wheeler transform
Manzini, G. (2001) · Journal of the ACM · doi:10.1145/382780.382782 · Cited by 375
Self-citationBentley, J., & Gries, D. (1987) · Communications of the ACM · doi:10.1145/32232.315727 · Cited by 329
The string B-tree: a new data structure for string search in external memory and its applications
Ferragina, P., & Grossi, R. (1999) · Journal of the ACM · doi:10.1145/301970.301973 · Cited by 317
Self-citation
Cited by
Fast and accurate short read alignment with Burrows-Wheeler transform
Li, H., & Durbin, R. (2009) · Bioinformatics · doi:10.1093/bioinformatics/btp324 · Cited by 58,607
Ultrafast and memory-efficient alignment of short DNA sequences to the human genome.
Langmead, B., Trapnell, C., Pop, M., & Salzberg, S. L. (2009) · Genome Biology · doi:10.1186/gb-2009-10-3-r25 · Cited by 21,849
Fast and accurate long-read alignment with Burrows-Wheeler transform.
Li, H., & Durbin, R. (2010) · Bioinformatics · doi:10.1093/bioinformatics/btp698 · Cited by 12,063
“FM-index (Ferragina and Manzini, 2000) is a compressed representation of the three arrays, consisting of the compressed BWT string B, auxiliary arrays for calculating O, and part of the suffix array S.”
InfluentialTranscript-level expression analysis of RNA-seq experiments with HISAT, StringTie and Ballgown
Pertea, M., Kim, D., Pertea, G. M., Leek, J. T., & Salzberg, S. L. (2016) · Nature Protocols · doi:10.1038/nprot.2016.095 · Cited by 6,845
Fast and sensitive taxonomic classification for metagenomics with Kaiju
Menzel, P., Ng, K. L., & Krogh, A. (2016) · Nature Communications · doi:10.1038/ncomms11257 · Cited by 2,118
De novo assembly of bacterial transcriptomes from RNA-seq data
Tjaden, B. (2015) · Genome Biology · doi:10.1186/s13059-014-0572-2 · Cited by 1,717
Centrifuge: rapid and sensitive classification of metagenomic sequences
Kim, D., Song, L., Breitwieser, F. P., & Salzberg, S. L. (2016) · Genome Research · doi:10.1101/gr.210641.116 · Cited by 1,438
“We have adapted this data structure, which is based on the Burrows-Wheeler transform (Burrows and Wheeler 1994) and the Ferragina-Manzini (FM) index (Ferragina and Manzini 2000), to create a metagenomics classifier, Centrifuge, that can efficiently store large numbers of genome sequences,…”
MethodAligning Short Sequencing Reads with Bowtie
Langmead, B. (2010) · Current Protocols in Bioinformatics · doi:10.1002/0471250953.bi1107s32 · Cited by 1,292
Adaptive seeds tame genomic sequence comparison
Kiełbasa, S. M., Wan, R., Sato, K., Horton, P., & Frith, M. C. (2011) · Genome Research · doi:10.1101/gr.113985.110 · Cited by 1,281
Chaisson, M. J., & Tesler, G. (2012) · BMC Bioinformatics · doi:10.1186/1471-2105-13-238 · Cited by 1,202
A survey of sequence alignment algorithms for next-generation sequencing
Li, H., & Homer, N. (2010) · Briefings in Bioinformatics · doi:10.1093/bib/bbq015 · Cited by 875
Efficient de novo assembly of large genomes using compressed data structures
Simpson, J. T., & Durbin, R. (2012) · Genome Research · doi:10.1101/gr.126953.111 · Cited by 768
High speed BLASTN: an accelerated MegaBLAST search tool
Chen, Y., Ye, W., Zhang, Y., & Xu, Y. (2015) · Nucleic Acids Research · doi:10.1093/nar/gkv784 · Cited by 744
Fast Identification and Removal of Sequence Contamination from Genomic and Metagenomic Datasets
Schmieder, R., & Edwards, R. (2011) · PLoS ONE · doi:10.1371/journal.pone.0017288 · Cited by 744
Navarro, G., & Mäkinen, V. (2007) · ACM Computing Surveys · doi:10.1145/1216370.1216372 · Cited by 735
From RNA-seq reads to differential expression results
Oshlack, A., Robinson, M. D., & Young, M. D. (2010) · Genome Biology · doi:10.1186/gb-2010-11-12-220 · Cited by 698
Ferragina, P., & Manzini, G. (2005) · Journal of the ACM · doi:10.1145/1082036.1082039 · Cited by 686
Self-citationReplacing suffix trees with enhanced suffix arrays
Abouelhoda, M. I., Kurtz, S., & Ohlebusch, E. (2004) · Journal of Discrete Algorithms · doi:10.1016/s1570-8667(03)00065-0 · Cited by 668
High-order entropy-compressed text indexes
Grossi, R., Gupta, A. K., & Vitter, J. S. (2003) · doi:10.5555/644108.644250 · Cited by 648
Benchmarking Metagenomics Tools for Taxonomic Classification
Ye, S. H., Siddle, K. J., Park, D. J., & Sabeti, P. C. (2019) · Cell · doi:10.1016/j.cell.2019.07.010 · Cited by 593
Computational analysis of bacterial RNA-Seq data
McClure, R., Balasubramanian, D., Sun, Y., Bobrovskyy, M., Sumby, P., Genco, C. A., Vanderpool, C. K., & Tjaden, B. (2013) · Nucleic Acids Research · doi:10.1093/nar/gkt444 · Cited by 591
Fast Mapping of Short Sequences with Mismatches, Insertions and Deletions Using Index Structures
Hoffmann, S., Otto, C., Kurtz, S., Sharma, C. M., Khaitovich, P., Vogel, J., Stadler, P. F., & Hackermüller, J. (2009) · PLoS Computational Biology · doi:10.1371/journal.pcbi.1000502 · Cited by 535
Nagarajan, N., & Pop, M. (2013) · Nature Reviews Genetics · doi:10.1038/nrg3367 · Cited by 474
Searching for SNPs with cloud computing
Langmead, B., Schatz, M. C., Lin, J., Pop, M., & Salzberg, S. L. (2009) · Genome Biology · doi:10.1186/gb-2009-10-11-r134 · Cited by 484
Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
Grossi, R., & Vitter, J. S. (2005) · SIAM Journal on Computing · doi:10.1137/s0097539702402354 · Cited by 431
Efficient haplotype matching and storage using the positional Burrows–Wheeler transform (PBWT)
Durbin, R. (2014) · Bioinformatics · doi:10.1093/bioinformatics/btu014 · Cited by 427
Exploring single-sample SNP and INDEL calling with whole-genome de novo assembly
Li, H. (2012) · Bioinformatics · doi:10.1093/bioinformatics/bts280 · Cited by 398
An analysis of the Burrows—Wheeler transform
Manzini, G. (2001) · Journal of the ACM · doi:10.1145/382780.382782 · Cited by 375
Self-citationCompressed representations of sequences and full-text indexes
Ferragina, P., Manzini, G., Mäkinen, V., & Navarro, G. (2007) · ACM Transactions on Algorithms · doi:10.1145/1240233.1240243 · Cited by 373
Self-citationAssembling the 20 Gb white spruce (Picea glauca) genome from whole-genome shotgun sequencing data
Birol, I., Raymond, A., Jackman, S. D., Pleasance, S., Coope, R., Taylor, G. A., Yuen, M. M. S., Keeling, C. I., Brand, D., Vandervalk, B. P., et al. (2013) · Bioinformatics · doi:10.1093/bioinformatics/btt178 · Cited by 367
Sense from sequence reads: methods for alignment and assembly
Flicek, P., & Birney, E. (2009) · Nature Methods · doi:10.1038/nmeth.1376 · Cited by 358
Denoising DNA deep sequencing data—high-throughput sequencing errors and their correction
Laehnemann, D., Borkhardt, A., & McHardy, A. C. (2016) · Briefings in Bioinformatics · doi:10.1093/bib/bbv029 · Cited by 296
Compressed Suffix Trees with Full Functionality
Sadakane, K. (2007) · Theory of Computing Systems · doi:10.1007/s00224-006-1198-x · Cited by 293
MOSAIK: A Hash-Based Algorithm for Accurate Next-Generation Sequencing Short-Read Mapping
Lee, W.-P., Stromberg, M. P., Ward, A., Stewart, C., Garrison, E. P., & Marth, G. T. (2014) · PLoS ONE · doi:10.1371/journal.pone.0090581 · Cited by 279
Targeted nanopore sequencing by real-time mapping of raw electrical signal with UNCALLED
Kovaka, S., Fan, Y., Ni, B., Timp, W., & Schatz, M. C. (2021) · Nature Biotechnology · doi:10.1038/s41587-020-0731-9 · Cited by 279
Efficient construction of an assembly string graph using the FM-index
Simpson, J. T., & Durbin, R. (2010) · Bioinformatics · doi:10.1093/bioinformatics/btq217 · Cited by 254
From Matching to Generation: A Survey on Generative Information Retrieval
Li, X., Jin, J., Zhou, Y., Zhang, Y., Zhang, P., Zhu, Y., & Dou, Z. (2025) · ACM Transactions on Information Systems · doi:10.1145/3722552 · Cited by 172
OLego: fast and sensitive mapping of spliced mRNA-Seq reads using small seeds
Wu, J., Anczuków, O., Krainer, A. R., Zhang, M. Q., & Zhang, C. (2013) · Nucleic Acids Research · doi:10.1093/nar/gkt216 · Cited by 123
Biology and medicine in the landscape of quantum advantages
Cordier, B. A., Sawaya, N. P. D., Guerreschi, G. G., & McWeeney, S. K. (2022) · Journal of The Royal Society Interface · doi:10.1098/rsif.2022.0541 · Cited by 87
Α Quantum Pattern Recognition Method for Improving Pairwise Sequence Alignment
Prousalis, K., & Konofaos, N. (2019) · Scientific Reports · doi:10.1038/s41598-019-43697-3 · Cited by 33
Multiview Identifiers Enhanced Generative Retrieval
Li, Y., Yang, N., Wang, L., Wei, F., & Li, W. (2023) · Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers) · doi:10.18653/v1/2023.acl-long.366 · Cited by 37
A Unified Generative Retriever for Knowledge-Intensive Language Tasks via Prompt Learning
Chen, J., Zhang, R., Guo, J., de Rijke, M., Liu, Y., Fan, Y., & Cheng, X. (2023) · Proceedings of the 46th International ACM SIGIR Conference on Research and Development in Information Retrieval · doi:10.1145/3539618.3591631 · Cited by 32
Learning to Rank in Generative Retrieval
Li, Y., Yang, N., Wang, L., Wei, F., & Li, W. (2023) · arXiv · doi:10.48550/arxiv.2306.15222 · Cited by 27
Learning to Rank in Generative Retrieval
Li, Y., Yang, N., Wang, L., Wei, F., & Li, W. (2024) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v38i8.28717 · Cited by 27
Metadata
- Authors
- Ferragina, P., & Manzini, G.
- Venue
- Proceedings 41st Annual Symposium on Foundations of Computer Science
- Publisher
- IEEE Comput. Soc
- Published
- 2002-11-07
- Pages
- 390-398
- ISSN
- 0272-5428 (ISSN-L)
- OpenAlex
- W2158322625
- Cited by
- 1,063
- References
- 15
- FWCI
- 18.21
- Type
- conference paper
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.