An experimental study of an opportunistic index
The DOI matches its OpenAlex record.
Abstract
The size of electronic data is currently growing at a faster rate than computer memory and disk storage capacities. For this reason compression appears always as an attractive choice, if not mandatory. However space overhead is not the only resource to be optimized when managing large data collections; in fact data turn out to be useful only when properly indexed to support search operations that efficiently extract the user-requested information. Approaches to combine compression and indexing techniques are nowadays receiving more and more attention. A rst step towards the design of a compressed full-text index achieving guaranteed performance in the worst case has been recently done in [10]. This index combines the compression algorithm proposed by Burrows and Wheeler [5] with the sux array data structure [16]. The index is opportunistic in that it takes advantage of the compressibility of the input data by decreasing the space occupancy at no signi cant asymptotic slowdown in the query performance. In this paper we present an implementation of this index and perform an extensive set of experiments on various text collections. The experiments show that our index is compact (its space occupancy is close to the one achieved by the best known compressors), it is fast in counting the number of pattern occurrences, and the cost of their retrieval is reasonable when they are few (i.e., in case of a selective query). In addition, our experiments show that the FM-index is exible in that it is possible to trade space occupancy for search time by choosing the amount of auxiliary information stored into it. 1
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
Cited by
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
TopHat: discovering splice junctions with RNA-Seq
Trapnell, C., Pachter, L., & Salzberg, S. L. (2009) · Bioinformatics · doi:10.1093/bioinformatics/btp120 · Cited by 11,617
Efficient Architecture-Aware Acceleration of BWA-MEM for Multicore Systems
Vasimuddin, M., Misra, S., Li, H., & Aluru, S. (2019) · 2019 IEEE International Parallel and Distributed Processing Symposium (IPDPS) · doi:10.1109/ipdps.2019.00041 · Cited by 3,000
Navarro, G., & Mäkinen, V. (2007) · ACM Computing Surveys · doi:10.1145/1216370.1216372 · Cited by 735
Replacing 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
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-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-citationBWA-MEME: BWA-MEM emulated with a machine learning approach
Jung, Y., & Han, D. (2022) · Bioinformatics · doi:10.1093/bioinformatics/btac137 · Cited by 331
Compressed Suffix Trees with Full Functionality
Sadakane, K. (2007) · Theory of Computing Systems · doi:10.1007/s00224-006-1198-x · Cited by 293
PRICE: Software for the Targeted Assembly of Components of (Meta) Genomic Sequence Data
Ruby, J. G., Bellare, P., & DeRisi, J. L. (2013) · G3 Genes|Genomes|Genetics · doi:10.1534/g3.113.005967 · Cited by 290
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
Metadata
- Authors
- Ferragina, P., & Manzini, G.
- Published
- 2001-01-09
- Volume
- 12
- Pages
- 269-278
- DOI
- 10.5555/365411.365458
- OpenAlex
- W2013697960
- Cited by
- 165
- References
- 0
- FWCI
- 11.64
- Type
- journal article
- 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.