{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,8]],"date-time":"2025-10-08T00:24:56Z","timestamp":1759883096708,"version":"build-2065373602"},"reference-count":47,"publisher":"Association for Computing Machinery (ACM)","issue":"1","funder":[{"name":"Basal Funds","award":["FB0001 and AFB240001"],"award-info":[{"award-number":["FB0001 and AFB240001"]}]},{"DOI":"10.13039\/501100020884","name":"ANID","doi-asserted-by":"crossref","award":["CHILE\/2020-21200906"],"award-info":[{"award-number":["CHILE\/2020-21200906"]}],"id":[{"id":"10.13039\/501100020884","id-type":"DOI","asserted-by":"crossref"}]},{"name":"NSERC Discovery","award":["RGPIN-07185-2020"],"award-info":[{"award-number":["RGPIN-07185-2020"]}]},{"name":"Fondecyt","award":["1-230755"],"award-info":[{"award-number":["1-230755"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2026,1,31]]},"abstract":"\n The\n \n r<\/jats:italic>\n -index\n <\/jats:sans-serif>\n (Gagie et al., JACM 2020) represented a breakthrough in compressed indexing of repetitive text collections, outperforming its alternatives by orders of magnitude in query time. Its space usage,\n \n \\(\\mathcal{O}(r)\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n where\n \n \\( r \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n is the number of runs in the Burrows\u2013Wheeler Transform of the text, is however higher than Lempel\u2013Ziv and grammar-based indexes and makes it uninteresting in various real-life scenarios of milder repetitiveness. In this article, we introduce the\n \n sr<\/jats:italic>\n -index\n <\/jats:sans-serif>\n , a variant that limits a large fraction of the space to\n \n \\({\\mathcal{O}}(\\min(r,n\/s))\\)<\/jats:tex-math>\n <\/jats:inline-formula>\n for a text of length\n \n \\( n \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n and a given parameter\n \n \\( s \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n , at the expense of multiplying by\n \n \\( s \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n the time per occurrence reported. The\n \n sr<\/jats:italic>\n -index\n <\/jats:sans-serif>\n is obtained by carefully subsampling the text positions indexed by the\n \n r<\/jats:italic>\n -index\n <\/jats:sans-serif>\n , in a way that we prove is still able to support pattern matching with guaranteed performance. Our experiments demonstrate that the theoretical analysis falls short in describing the practical advantages of the\n \n sr<\/jats:italic>\n -index\n <\/jats:sans-serif>\n , because it performs much better on real texts than on synthetic ones: the\n \n sr<\/jats:italic>\n -index\n <\/jats:sans-serif>\n retains the performance of the\n \n r<\/jats:italic>\n -index\n <\/jats:sans-serif>\n while using 1.5\u20134.0 times less space, sharply outperforming\n virtually every other<\/jats:italic>\n compressed index on repetitive texts in both time and space. Only a particular Lempel\u2013Ziv-based index uses less space\u2014about half\u2014than the\n \n sr<\/jats:italic>\n -index\n <\/jats:sans-serif>\n , but it is an order of magnitude slower.\n <\/jats:p>\n \n Our second contribution are the\n \n r<\/jats:italic>\n -csa\n <\/jats:sans-serif>\n and\n \n sr<\/jats:italic>\n -csa\n <\/jats:sans-serif>\n indexes. Just like the\n \n r<\/jats:italic>\n -index\n <\/jats:sans-serif>\n adapts the well-known FM-Index to repetitive texts, the\n \n r<\/jats:italic>\n -csa\n <\/jats:sans-serif>\n adapts Sadakane\u2019s Compressed Suffix Array (CSA) to this case. We show that the principles used on the\n \n r<\/jats:italic>\n -index\n <\/jats:sans-serif>\n turn out to fit naturally and efficiently in the CSA framework. The\n \n sr<\/jats:italic>\n -csa\n <\/jats:sans-serif>\n is the corresponding subsampled version of the\n \n r<\/jats:italic>\n -csa\n <\/jats:sans-serif>\n . While the CSA performs better than the FM-Index on classic texts with alphabets larger than DNA, our experiments show that the\n \n sr<\/jats:italic>\n -csa\n <\/jats:sans-serif>\n outperforms the\n \n sr<\/jats:italic>\n -index\n <\/jats:sans-serif>\n on repetitive texts not only over those larger alphabets, but on some DNA texts as well.\n <\/jats:p>\n \n Overall, our new subsampled indexes sweep the table of the existing indexes for highly repetitive text collection, by combining the exceptional speed of the\n \n r<\/jats:italic>\n -index\n <\/jats:sans-serif>\n with drastically reduced storage use.\n <\/jats:p>","DOI":"10.1145\/3750729","type":"journal-article","created":{"date-parts":[[2025,8,18]],"date-time":"2025-08-18T15:59:14Z","timestamp":1755532754000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Fast and Small Subsampled R-indexes"],"prefix":"10.1145","volume":"22","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6081-694X","authenticated-orcid":false,"given":"Dustin","family":"Cobas","sequence":"first","affiliation":[{"name":"CeBiB\u2014Center for Biotechnology and Bioengineering, Santiago, Chile, and University of Chile, Santiago, Chile"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3689-327X","authenticated-orcid":false,"given":"Travis","family":"Gagie","sequence":"additional","affiliation":[{"name":"CeBiB\u2014Center for Biotechnology and Bioengineering, Santiago, Chile, and Dalhousie University, Halifax, Nova Scotia, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2286-741X","authenticated-orcid":false,"given":"Gonzalo","family":"Navarro","sequence":"additional","affiliation":[{"name":"CeBiB\u2014Center for Biotechnology and Bioengineering, Santiago, Chile, and University of Chile, Santiago, Chile"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,10,7]]},"reference":[{"key":"e_1_3_2_2_2","first-page":"178","volume-title":"Proceedings of the Latin American Symposium on Theoretical Informatics (LATIN)","author":"Bal\u00e1\u017e Andrej","year":"2024","unstructured":"Andrej Bal\u00e1\u017e, Travis Gagie, Adri\u00e1n Goga, Simon Heumos, Gonzalo Navarro, Alessia Petescia, and Jouni Sir\u00e9n. 2024. Wheeler maps. In Proceedings of the Latin American Symposium on Theoretical Informatics (LATIN), 178\u2013192."},{"issue":"4","key":"e_1_3_2_3_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2629339","article-title":"Optimal lower and upper bounds for representing sequences","volume":"11","author":"Belazzougui Djamal","unstructured":"Djamal Belazzougui and Gonzalo Navarro. 2015. Optimal lower and upper bounds for representing sequences. ACM Transactions on Algorithms 11, 4 (2015), Article 31, 1\u201321.","journal-title":"ACM Transactions on Algorithms"},{"key":"e_1_3_2_4_2","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1137\/1.9781611976472.5","volume-title":"Proceedings of the 23rd Workshop on Algorithm Engineering and Experiments (ALENEX)","author":"Boucher Christina","year":"2021","unstructured":"Christina Boucher, Ondrej Cvacho, Travis Gagie, Jan Holub, Giovanni Manzini, Gonzalo Navarro, and Massimiliano Rossi. 2021. PFP compressed suffix trees. In Proceedings of the 23rd Workshop on Algorithm Engineering and Experiments (ALENEX), 60\u201372."},{"key":"e_1_3_2_5_2","volume-title":"A Block-Sorting Lossless Data Compression Algorithm","author":"Burrows Michael","year":"1994","unstructured":"Michael Burrows and David J. Wheeler. 1994. A Block-Sorting Lossless Data Compression Algorithm. Technical Report 124. Digital Equipment Corporation."},{"key":"e_1_3_2_6_2","article-title":"Faster repetition-aware compressed suffix trees based on block trees","volume":"285","author":"C\u00e1ceres Manuel","year":"2022","unstructured":"Manuel C\u00e1ceres and Gonzalo Navarro. 2022. Faster repetition-aware compressed suffix trees based on block trees. Information and Computation 285B (2022), Article 104749.","journal-title":"Information and Computation"},{"key":"e_1_3_2_7_2","volume-title":"Compact PAT Trees","author":"Clark David R.","year":"1996","unstructured":"David R. Clark. 1996. Compact PAT Trees. Ph.D. Dissertation. University of Waterloo, Canada."},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2020.12.001"},{"key":"e_1_3_2_9_2","first-page":"1","volume-title":"Proceedings of the 32nd Annual Symposium on Combinatorial Pattern Matching (CPM)","volume":"13","author":"Cobas Dustin","year":"2021","unstructured":"Dustin Cobas, Travis Gagie, and Gonzalo Navarro. 2021. A fast and small subsampled r-index. In Proceedings of the 32nd Annual Symposium on Combinatorial Pattern Matching (CPM), 13:1\u201313:16."},{"key":"e_1_3_2_10_2","doi-asserted-by":"crossref","unstructured":"Lore Depuydt Omar Ahmed Jan Fostier Travis Gagie and Ben Langmead. 2025. Run-length compressed metagenomic read classification with SMEM-finding and tagging. bioRxiv:2025.02.25.640119. Retrieved from https:\/\/www.biorxiv.org\/content\/10.1101\/2025.02.25.640119v2","DOI":"10.1101\/2025.02.25.640119"},{"key":"e_1_3_2_11_2","first-page":"93","volume-title":"Proceedings of the 31st Data Compression Conference (DCC)","author":"D\u00edaz-Dom\u00ednguez Diego","year":"2021","unstructured":"Diego D\u00edaz-Dom\u00ednguez and Gonzalo Navarro. 2021. A grammar compressor for collections of reads with applications to the construction of the BWT. In Proceedings of the 31st Data Compression Conference (DCC), 93\u2013102."},{"key":"e_1_3_2_12_2","first-page":"1","volume-title":"Proceedings of the 20th Workshop on Algorithm Engineering and Experiments (ALENEX)","author":"Ferrada H\u00e9ctor","year":"2018","unstructured":"H\u00e9ctor Ferrada, Dominik Kempa, and Simon J. Puglisi. 2018. Hybrid indexing revisited. In Proceedings of the 20th Workshop on Algorithm Engineering and Experiments (ALENEX), 1\u20138."},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/1082036.1082039"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/1240233.1240243"},{"key":"e_1_3_2_15_2","unstructured":"Paolo Ferragina and Gonzalo Navarro. The Pizza&Chili Repetitive Corpus. Retrieved September 2024 from http:\/\/pizzachili.dcc.uchile.cl\/repcorpus.html"},{"key":"e_1_3_2_16_2","volume-title":"Encyclopedia of Big Data Technologies","author":"Gagie Travis","year":"2019","unstructured":"Travis Gagie and Gonzalo Navarro. 2019. Compressed indexes for repetitive textual datasets. In Encyclopedia of Big Data Technologies. Springer."},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/3375890"},{"key":"e_1_3_2_18_2","first-page":"123","volume-title":"Proceedings of the 34th Data Compression Conference (DCC)","author":"Goga Adri\u00e1n","year":"2024","unstructured":"Adri\u00e1n Goga, Lore Depuydt, Nathaniel K. Brown, Jan Fostier, Travis Gagie, and Gonzalo Navarro. 2024. Faster maximal exact matches with lazy LCP evaluation. In Proceedings of the 34th Data Compression Conference (DCC), 123\u2013132."},{"key":"e_1_3_2_19_2","first-page":"368","volume-title":"Proceedings of the 17th ACM-SIAM Annual Symposium on Discrete Algorithms (SODA)","author":"Golynski Alexander","year":"2006","unstructured":"Alexander Golynski, J. Ian Munro, and S. Srinivasa Rao. 2006. Rank\/select operations on large alphabets: A tool for text indexing. In Proceedings of the 17th ACM-SIAM Annual Symposium on Discrete Algorithms (SODA), 368\u2013373."},{"issue":"1","key":"e_1_3_2_20_2","article-title":"Locally compressed suffix arrays","volume":"19","author":"Gonz\u00e1lez Rodrigo","year":"2014","unstructured":"Rodrigo Gonz\u00e1lez, Gonzalo Navarro, and H\u00e9ctor Ferrada. 2014. Locally compressed suffix arrays. ACM Journal of Experimental Algorithmics 19, 1 (2014), Article 1.1, 1.1:1\u20131.1:30.","journal-title":"ACM Journal of Experimental Algorithmics"},{"key":"e_1_3_2_21_2","first-page":"841","volume-title":"Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Grossi Robrtyo","year":"2003","unstructured":"Robrtyo Grossi, Ankur Gupta, and Jeffrey S. Vitter. 2003. High-order entropy-compressed text indexes. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 841\u2013850."},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702402354"},{"key":"e_1_3_2_23_2","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1007\/978-3-642-02441-2_17","volume-title":"Proceedings of the 20th Annual Symposium on Combinatorial Pattern Matching (CPM)","author":"K\u00e4rkk\u00e4inen Juha","year":"2009","unstructured":"Juha K\u00e4rkk\u00e4inen, Giovanni Manzini, and Simon J. Puglisi. 2009. Permuted longest-common-prefix array. In Proceedings of the 20th Annual Symposium on Combinatorial Pattern Matching (CPM), 181\u2013192."},{"key":"e_1_3_2_24_2","doi-asserted-by":"crossref","first-page":"174","DOI":"10.1007\/978-3-642-24583-1_18","volume-title":"Proceedings of the 18th International Symposium on String Processing and Information Retrieval (SPIRE)","author":"K\u00e4rkk\u00e4inen Juha","year":"2011","unstructured":"Juha K\u00e4rkk\u00e4inen and Simon J. Puglisi. 2011. Fixed block compression boosting in FM-Indexes. In Proceedings of the 18th International Symposium on String Processing and Information Retrieval (SPIRE), 174\u2013184."},{"key":"e_1_3_2_25_2","first-page":"1002","volume-title":"Proceedings of the 61st IEEE Symposium on Foundations of Computer Science (FOCS)","author":"Kempa Dominik","year":"2020","unstructured":"Dominik Kempa and Tomasz Kociumaka. 2020. Resolution of the burrows\u2013wheeler transform conjecture. In Proceedings of the 61st IEEE Symposium on Foundations of Computer Science (FOCS), 1002\u20131013."},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1109\/18.841160"},{"key":"e_1_3_2_27_2","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1016\/j.tcs.2012.02.006","article-title":"On compressing and indexing repetitive sequences","volume":"483","author":"Kreft Sebastian","year":"2013","unstructured":"Sebastian Kreft and Gonzalo Navarro. 2013. On compressing and indexing repetitive sequences. Theoretical Computer Science 483 (2013), 115\u2013133.","journal-title":"Theoretical Computer Science"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1976.1055501"},{"key":"e_1_3_2_29_2","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/bts280"},{"key":"e_1_3_2_30_2","unstructured":"Heng Li. 2024. BWT construction and search at the terabase scale. arXiv:2409.00613. Retrieved from https:\/\/arxiv.org\/abs\/2409.00613"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139940023"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.5555\/1195881.1195885"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1145\/1367064.1367072"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2009.0169"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1137\/0222058"},{"issue":"2","key":"e_1_3_2_36_2","first-page":"1","article-title":"Indexing highly repetitive string collections, part II: Compressed indexes","volume":"54","author":"Navarro Gonzalo","year":"2021","unstructured":"Gonzalo Navarro. 2021. Indexing highly repetitive string collections, part II: Compressed indexes. ACM Computing Surveys 54, 2 (2021), Article 26, 1\u201332.","journal-title":"ACM Computing Surveys"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1145\/1216370.1216372"},{"issue":"1","key":"e_1_3_2_38_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2851495","article-title":"Faster compressed suffix trees for repetitive collections","volume":"21","author":"Navarro Gonzalo","year":"2016","unstructured":"Gonzalo Navarro and Alberto Ord\u00f3\u00f1ez. 2016. Faster compressed suffix trees for repetitive collections. ACM Journal of Experimental Algorithmics 21, 1 (2016), Article 1.8, 1\u201338.","journal-title":"ACM Journal of Experimental Algorithmics"},{"key":"e_1_3_2_39_2","first-page":"201","volume-title":"Proceedings of the 29th Data Compression Conference (DCC)","author":"Navarro Gonzalo","year":"2019","unstructured":"Gonzalo Navarro and V\u00edctor Sep\u00falveda. 2019. Practical indexing of repetitive collections using relative Lempel\u2013Ziv. In Proceedings of the 29th Data Compression Conference (DCC), 201\u2013210."},{"key":"e_1_3_2_40_2","unstructured":"Takaaki Nishimoto and Yasuo Tabei. 2020. Faster queries on BWT-runs compressed indexes. arXiv:2006.05104. Retrieved from https:\/\/arxiv.org\/abs\/2006.05104v1"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972870.6"},{"key":"e_1_3_2_42_2","volume-title":"Compressed Computation for Text Indexing","author":"Prezza Nicola","year":"2017","unstructured":"Nicola Prezza. 2017. Compressed Computation for Text Indexing. Ph.D. Dissertation. University of Udine, Italy."},{"key":"e_1_3_2_43_2","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1007\/978-3-030-59212-7_7","volume-title":"Proceedings of the 27th International Symposium on String Processing and Information Retrieval (SPIRE)","author":"Puglisi Simon J.","year":"2020","unstructured":"Simon J. Puglisi and Bella Zhukova. 2020. Relative Lempel\u2013Ziv compression of suffix arrays. In Proceedings of the 27th International Symposium on String Processing and Information Retrieval (SPIRE), 89\u201396."},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2021.0290"},{"key":"e_1_3_2_45_2","first-page":"225","volume-title":"Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Sadakane Kunihiko","year":"2002","unstructured":"Kunihiko Sadakane. 2002. Succinct representations of \\(lcp\\) information and improvements in the compressed suffix arrays. In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 225\u2013232."},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0196-6774(03)00087-7"},{"key":"e_1_3_2_47_2","doi-asserted-by":"publisher","DOI":"10.3389\/fmicb.2017.00808"},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1038\/nature15393"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3750729","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,7]],"date-time":"2025-10-07T15:06:04Z","timestamp":1759849564000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3750729"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,7]]},"references-count":47,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,1,31]]}},"alternative-id":["10.1145\/3750729"],"URL":"https:\/\/doi.org\/10.1145\/3750729","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2025,10,7]]},"assertion":[{"value":"2024-09-18","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-07-20","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-10-07","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}