{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,29]],"date-time":"2026-07-29T13:57:48Z","timestamp":1785333468425,"version":"3.55.0"},"reference-count":117,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2020,1,15]],"date-time":"2020-01-15T00:00:00Z","timestamp":1579046400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"MIUR-SIR CMACBioSeq","award":["RBSI146R5L"],"award-info":[{"award-number":["RBSI146R5L"]}]},{"name":"Basal Funds FB0001 and Fondecyt","award":["1-171058 and 1-170048"],"award-info":[{"award-number":["1-171058 and 1-170048"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2020,2,29]]},"abstract":"<jats:p>\n            Indexing highly repetitive texts\u2014such as genomic databases, software repositories and versioned text collections\u2014has become an important problem since the turn of the millennium. A relevant compressibility measure for repetitive texts is\n            <jats:italic>r<\/jats:italic>\n            , the number of runs in their Burrows-Wheeler Transforms (BWTs). One of the earliest indexes for repetitive collections, the Run-Length FM-index, used\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>r<\/jats:italic>\n            ) space and was able to efficiently count the number of occurrences of a pattern of length\n            <jats:italic>m<\/jats:italic>\n            in a text of length\n            <jats:italic>n<\/jats:italic>\n            (in\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>m<\/jats:italic>\n            log log\n            <jats:italic>n<\/jats:italic>\n            ) time, with current techniques). However, it was unable to locate the positions of those occurrences efficiently within a space bounded in terms of\n            <jats:italic>r<\/jats:italic>\n            . In this article, we close this long-standing problem, showing how to extend the Run-Length FM-index so that it can locate the\n            <jats:italic>occ<\/jats:italic>\n            occurrences efficiently (in\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>occ<\/jats:italic>\n            log log\n            <jats:italic>n<\/jats:italic>\n            ) time) within\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>r<\/jats:italic>\n            ) space. By raising the space to\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>r<\/jats:italic>\n            log log\n            <jats:italic>n<\/jats:italic>\n            ), our index counts the occurrences in optimal time,\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>m<\/jats:italic>\n            ), and locates them in optimal time as well,\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>m<\/jats:italic>\n            +\n            <jats:italic>occ<\/jats:italic>\n            ). By further raising the space by an\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>w<\/jats:italic>\n            \/ log \u03c3) factor, where \u03c3 is the alphabet size and\n            <jats:italic>w<\/jats:italic>\n            = \u03a9 (log\n            <jats:italic>n<\/jats:italic>\n            ) is the RAM machine size in bits, we support count and locate in\n            <jats:italic>O<\/jats:italic>\n            (\u2308\n            <jats:italic>m<\/jats:italic>\n            log (\u03c3)\/\n            <jats:italic>w<\/jats:italic>\n            \u2309) and\n            <jats:italic>O<\/jats:italic>\n            (\u2308\n            <jats:italic>m<\/jats:italic>\n            log (\u03c3)\/\n            <jats:italic>w<\/jats:italic>\n            \u2309 +\n            <jats:italic>occ<\/jats:italic>\n            ) time, which is optimal in the packed setting and had not been obtained before in compressed space. We also describe a structure using\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>r<\/jats:italic>\n            log (\n            <jats:italic>n<\/jats:italic>\n            \/\n            <jats:italic>r<\/jats:italic>\n            )) space that replaces the text and extracts any text substring of length \u2113 in the almost-optimal time\n            <jats:italic>O<\/jats:italic>\n            (log (\n            <jats:italic>n<\/jats:italic>\n            \/\n            <jats:italic>r<\/jats:italic>\n            )+\u2113 log (\u03c3)\/\n            <jats:italic>w<\/jats:italic>\n            ). Within that space, we similarly provide access to arbitrary suffix array, inverse suffix array, and longest common prefix array cells in time\n            <jats:italic>O<\/jats:italic>\n            (log (\n            <jats:italic>n<\/jats:italic>\n            \/\n            <jats:italic>r<\/jats:italic>\n            )), and extend these capabilities to full suffix tree functionality, typically in\n            <jats:italic>O<\/jats:italic>\n            (log (\n            <jats:italic>n<\/jats:italic>\n            \/\n            <jats:italic>r<\/jats:italic>\n            )) time per operation. Our experiments show that our\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>r<\/jats:italic>\n            )-space index outperforms the space-competitive alternatives by 1--2 orders of magnitude in time. Competitive implementations of the original FM-index are outperformed by 1--2 orders of magnitude in space and\/or 2--3 in time.\n          <\/jats:p>","DOI":"10.1145\/3375890","type":"journal-article","created":{"date-parts":[[2020,1,16]],"date-time":"2020-01-16T03:49:06Z","timestamp":1579146546000},"page":"1-54","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":130,"title":["Fully Functional Suffix Trees and Optimal Text Searching in BWT-Runs Bounded Space"],"prefix":"10.1145","volume":"67","author":[{"given":"Travis","family":"Gagie","sequence":"first","affiliation":[{"name":"Dalhousie University, Halifax, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gonzalo","family":"Navarro","sequence":"additional","affiliation":[{"name":"University of Chile, Santiago, Chile"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Nicola","family":"Prezza","sequence":"additional","affiliation":[{"name":"University of Pisa, Pisa, Rome, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,1,15]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.3390\/a6020319"},{"key":"e_1_2_1_2_1","volume-title":"Proc. 29th Annual Symposium on Combinatorial Pattern Matching (CPM). 7:1--7:12","author":"Bannai H.","year":"2018","unstructured":"H. Bannai , T. Gagie , and T. I. 2018 . Online LZ77 parsing and matching statistics with RLBWTs . In Proc. 29th Annual Symposium on Combinatorial Pattern Matching (CPM). 7:1--7:12 . H. Bannai, T. Gagie, and T. I. 2018. Online LZ77 parsing and matching statistics with RLBWTs. In Proc. 29th Annual Symposium on Combinatorial Pattern Matching (CPM). 7:1--7:12."},{"key":"e_1_2_1_3_1","volume-title":"Proc. 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 785--794","author":"Belazzougui D.","unstructured":"D. Belazzougui , P. Boldi , R. Pagh , and S. Vigna . 2009a. Monotone minimal perfect hashing: Searching a sorted table with O(1) accesses . In Proc. 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 785--794 . D. Belazzougui, P. Boldi, R. Pagh, and S. Vigna. 2009a. Monotone minimal perfect hashing: Searching a sorted table with O(1) accesses. In Proc. 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 785--794."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1963190.2025378"},{"key":"e_1_2_1_5_1","unstructured":"D. Belazzougui P. Boldi R. Pagh and S. Vigna. 2018. Fast prefix search in little space with applications. CoRR 1804.04720 (2018).  D. Belazzougui P. Boldi R. Pagh and S. Vigna. 2018. Fast prefix search in little space with applications. CoRR 1804.04720 (2018)."},{"key":"e_1_2_1_6_1","volume-title":"Proc. 17th Annual European Symposium (ESA). 682--693","author":"Belazzougui D.","unstructured":"D. Belazzougui , F. C. Botelho , and M. Dietzfelbinger . 2009b. Hash, displace, and compress . In Proc. 17th Annual European Symposium (ESA). 682--693 . D. Belazzougui, F. C. Botelho, and M. Dietzfelbinger. 2009b. Hash, displace, and compress. In Proc. 17th Annual European Symposium (ESA). 682--693."},{"key":"e_1_2_1_7_1","volume-title":"Proc. 24th International Symposium on String Processing and Information Retrieval (SPIRE). 161--175","author":"Belazzougui D.","unstructured":"D. Belazzougui and F. Cunial . 2017a. Fast label extraction in the CDAWG . In Proc. 24th International Symposium on String Processing and Information Retrieval (SPIRE). 161--175 . D. Belazzougui and F. Cunial. 2017a. Fast label extraction in the CDAWG. In Proc. 24th International Symposium on String Processing and Information Retrieval (SPIRE). 161--175."},{"key":"e_1_2_1_8_1","volume-title":"Proc. 28th Annual Symposium on Combinatorial Pattern Matching (CPM). 7:1--7:13","author":"Belazzougui D.","unstructured":"D. Belazzougui and F. Cunial . 2017b. Representing the suffix tree with the CDAWG . In Proc. 28th Annual Symposium on Combinatorial Pattern Matching (CPM). 7:1--7:13 . D. Belazzougui and F. Cunial. 2017b. Representing the suffix tree with the CDAWG. In Proc. 28th Annual Symposium on Combinatorial Pattern Matching (CPM). 7:1--7:13."},{"key":"e_1_2_1_9_1","volume-title":"Proc. 26th Annual Symposium on Combinatorial Pattern Matching (CPM). 26--39","author":"Belazzougui D.","unstructured":"D. Belazzougui , F. Cunial , T. Gagie , N. Prezza , and M. Raffinot . 2015a. Composite repetition-aware data structures . In Proc. 26th Annual Symposium on Combinatorial Pattern Matching (CPM). 26--39 . D. Belazzougui, F. Cunial, T. Gagie, N. Prezza, and M. Raffinot. 2015a. Composite repetition-aware data structures. In Proc. 26th Annual Symposium on Combinatorial Pattern Matching (CPM). 26--39."},{"key":"e_1_2_1_10_1","volume-title":"Proc. 25th Data Compression Conference (DCC). 83--92","author":"Belazzougui D.","unstructured":"D. Belazzougui , T. Gagie , P. Gawrychowski , J. K\u00e4rkk\u00e4inen , A. Ord\u00f3\u00f1ez , S. J. Puglisi , and Y. Tabei . 2015b. Queries on LZ-bounded encodings . In Proc. 25th Data Compression Conference (DCC). 83--92 . D. Belazzougui, T. Gagie, P. Gawrychowski, J. K\u00e4rkk\u00e4inen, A. Ord\u00f3\u00f1ez, S. J. Puglisi, and Y. Tabei. 2015b. Queries on LZ-bounded encodings. In Proc. 25th Data Compression Conference (DCC). 83--92."},{"key":"e_1_2_1_11_1","volume-title":"Relative FM-indexes. In Proc. 21st International Symposium on String Processing and Information Retrieval (SPIRE). 52--64","author":"Belazzougui D.","unstructured":"D. Belazzougui , T. Gagie , S. Gog , G. Manzini , and J. Sir\u00e9n . 2014 . Relative FM-indexes. In Proc. 21st International Symposium on String Processing and Information Retrieval (SPIRE). 52--64 . D. Belazzougui, T. Gagie, S. Gog, G. Manzini, and J. Sir\u00e9n. 2014. Relative FM-indexes. In Proc. 21st International Symposium on String Processing and Information Retrieval (SPIRE). 52--64."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2635816"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2629339"},{"key":"e_1_2_1_14_1","volume-title":"Proc. 23rd Annual European Symposium on Algorithms (ESA). 142--154","author":"Belazzougui D.","unstructured":"D. Belazzougui , S. J. Puglisi , and Y. Tabei . 2015c. Access, rank, select in grammar-compressed strings . In Proc. 23rd Annual European Symposium on Algorithms (ESA). 142--154 . D. Belazzougui, S. J. Puglisi, and Y. Tabei. 2015c. Access, rank, select in grammar-compressed strings. In Proc. 23rd Annual European Symposium on Algorithms (ESA). 142--154."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2017.12.021"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/130936889"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/28869.28873"},{"key":"e_1_2_1_18_1","volume-title":"Prefix-free parsing for building big BWTs. Algorithms for Molecular Biology 14, 1","author":"Boucher Christina","year":"2019","unstructured":"Christina Boucher , Travis Gagie , Alan Kuhnle , Ben Langmead , Giovanni Manzini , and Taher Mun . 2019. Prefix-free parsing for building big BWTs. Algorithms for Molecular Biology 14, 1 ( 2019 ), 13:1--13:15. Christina Boucher, Travis Gagie, Alan Kuhnle, Ben Langmead, Giovanni Manzini, and Taher Mun. 2019. Prefix-free parsing for building big BWTs. Algorithms for Molecular Biology 14, 1 (2019), 13:1--13:15."},{"key":"e_1_2_1_19_1","volume-title":"Proc. 18th International Workshop on Algorithms in Bioinformatics (WABI). 2:1--2:16","author":"Boucher C.","unstructured":"C. Boucher , T. Gagie , A. Kuhnle , and G. Manzini . 2018. Prefix-free parsing for building big BWTs . In Proc. 18th International Workshop on Algorithms in Bioinformatics (WABI). 2:1--2:16 . C. Boucher, T. Gagie, A. Kuhnle, and G. Manzini. 2018. Prefix-free parsing for building big BWTs. In Proc. 18th International Workshop on Algorithms in Bioinformatics (WABI). 2:1--2:16."},{"key":"e_1_2_1_20_1","volume-title":"Technical Report 124. Digital Equipment Corporation.","author":"Burrows M.","year":"1994","unstructured":"M. Burrows and D. Wheeler . 1994 . A Block Sorting Lossless Data Compression Algorithm . Technical Report 124. Digital Equipment Corporation. M. Burrows and D. Wheeler. 1994. A Block Sorting Lossless Data Compression Algorithm. Technical Report 124. Digital Equipment Corporation."},{"key":"e_1_2_1_21_1","volume-title":"Proc. 26th International Symposium on String Processing and Information Retrieval (SPIRE). To appear.","author":"C\u00e1ceres M.","unstructured":"M. C\u00e1ceres and G. Navarro . 2019. Faster repetition-aware compressed suffix trees based on block trees . In Proc. 26th International Symposium on String Processing and Information Retrieval (SPIRE). To appear. M. C\u00e1ceres and G. Navarro. 2019. Faster repetition-aware compressed suffix trees based on block trees. In Proc. 26th International Symposium on String Processing and Information Retrieval (SPIRE). To appear."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.850116"},{"key":"e_1_2_1_23_1","unstructured":"S. Chen E. Verbin and W. Yu. 2012. Data structure lower bounds on random access to grammar-compressed strings. CoRR 1203.1080 (2012).  S. Chen E. Verbin and W. Yu. 2012. Data structure lower bounds on random access to grammar-compressed strings. CoRR 1203.1080 (2012)."},{"key":"e_1_2_1_24_1","volume-title":"Proc. 13th Latin American Symposium on Theoretical Informatics (LATIN). 331--345","author":"Christiansen A. R.","unstructured":"A. R. Christiansen and M. B. Ettienne . 2018. Compressed indexing with signature grammars . In Proc. 13th Latin American Symposium on Theoretical Informatics (LATIN). 331--345 . A. R. Christiansen and M. B. Ettienne. 2018. Compressed indexing with signature grammars. In Proc. 13th Latin American Symposium on Theoretical Informatics (LATIN). 331--345."},{"key":"e_1_2_1_25_1","unstructured":"A. R. Christiansen M. B. Ettienne T. Kociumaka G. Navarro and N. Prezza. 2019. Optimal-time dictionary-compressed indexes. CoRR 1811.12779v3 (2019).  A. R. Christiansen M. B. Ettienne T. Kociumaka G. Navarro and N. Prezza. 2019. Optimal-time dictionary-compressed indexes. CoRR 1811.12779v3 (2019)."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2016.04.002"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/2361502.2361504"},{"key":"e_1_2_1_28_1","volume-title":"Proc. 19th International Symposium on String Processing and Information Retrieval (SPIRE). 180--192","author":"Claude F.","unstructured":"F. Claude and G. Navarro . 2012. Improved grammar-based compressed indexes . In Proc. 19th International Symposium on String Processing and Information Retrieval (SPIRE). 180--192 . F. Claude and G. Navarro. 2012. Improved grammar-based compressed indexes. In Proc. 19th International Symposium on String Processing and Information Retrieval (SPIRE). 180--192."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2013.07.024"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/355541.355547"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/bxx108"},{"key":"e_1_2_1_32_1","unstructured":"H. Ferrada T. Gagie T. Hirvola and S. J. Puglisi. 2013. Hybrid indexes for repetitive datasets. CoRR 1306.4037 (2013).  H. Ferrada T. Gagie T. Hirvola and S. J. Puglisi. 2013. Hybrid indexes for repetitive datasets. CoRR 1306.4037 (2013)."},{"key":"e_1_2_1_33_1","volume-title":"Proc. 20th Workshop on Algorithm Engineering and Experiments (ALENEX). 1--8.","author":"Ferrada H.","unstructured":"H. Ferrada , D. Kempa , and S. J. Puglisi . 2018. Hybrid indexing revisited . In Proc. 20th Workshop on Algorithm Engineering and Experiments (ALENEX). 1--8. H. Ferrada, D. Kempa, and S. J. Puglisi. 2018. Hybrid indexing revisited. In Proc. 20th Workshop on Algorithm Engineering and Experiments (ALENEX). 1--8."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1082036.1082039"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1240233.1240243"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2010.02.010"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11786-009-0007-8"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1137\/090779759"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.09.012"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/828.1884"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90040-4"},{"key":"e_1_2_1_42_1","doi-asserted-by":"crossref","unstructured":"M. H.-Y. Fritz R. Leinonen G. Cochrane and E. Birney. 2011. Efficient storage of high throughput DNA sequencing data using reference-based compression. Genome Research (2011) 734--740.  M. H.-Y. Fritz R. Leinonen G. Cochrane and E. Birney. 2011. Efficient storage of high throughput DNA sequencing data using reference-based compression. Genome Research (2011) 734--740.","DOI":"10.1101\/gr.114819.110"},{"key":"e_1_2_1_43_1","volume-title":"Proc. 6th International Conference on Language and Automata Theory and Applications (LATA). 240--251","author":"Gagie T.","unstructured":"T. Gagie , P. Gawrychowski , J. K\u00e4rkk\u00e4inen , Y. Nekrich , and S. J. Puglisi . 2012. A faster grammar-based self-index . In Proc. 6th International Conference on Language and Automata Theory and Applications (LATA). 240--251 . T. Gagie, P. Gawrychowski, J. K\u00e4rkk\u00e4inen, Y. Nekrich, and S. J. Puglisi. 2012. A faster grammar-based self-index. In Proc. 6th International Conference on Language and Automata Theory and Applications (LATA). 240--251."},{"key":"e_1_2_1_44_1","volume-title":"Proc. 11th Latin American Symposium on Theoretical Informatics (LATIN). 731--742","author":"Gagie T.","unstructured":"T. Gagie , P Gawrychowski , J. K\u00e4rkk\u00e4inen , Y. Nekrich , and S. J. Puglisi . 2014. LZ77-based self-indexing with faster pattern matching . In Proc. 11th Latin American Symposium on Theoretical Informatics (LATIN). 731--742 . T. Gagie, P Gawrychowski, J. K\u00e4rkk\u00e4inen, Y. Nekrich, and S. J. Puglisi. 2014. LZ77-based self-indexing with faster pattern matching. In Proc. 11th Latin American Symposium on Theoretical Informatics (LATIN). 731--742."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2014.10.003"},{"key":"e_1_2_1_46_1","unstructured":"T. Gagie G. Navarro and N. Prezza. 2017. Optimal-time text indexing in BWT-runs bounded space. CoRR 1705.10382v4 (2017).  T. Gagie G. Navarro and N. Prezza. 2017. Optimal-time text indexing in BWT-runs bounded space. CoRR 1705.10382v4 (2017)."},{"key":"e_1_2_1_47_1","volume-title":"Proc. 13th Latin American Symposium on Theoretical Informatics (LATIN). 490--503","author":"Gagie T.","unstructured":"T. Gagie , G. Navarro , and N. Prezza . 2018a. On the approximation ratio of Lempel-Ziv parsing . In Proc. 13th Latin American Symposium on Theoretical Informatics (LATIN). 490--503 . T. Gagie, G. Navarro, and N. Prezza. 2018a. On the approximation ratio of Lempel-Ziv parsing. In Proc. 13th Latin American Symposium on Theoretical Informatics (LATIN). 490--503."},{"key":"e_1_2_1_48_1","volume-title":"Proc. 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 1459--1477","author":"Gagie T.","unstructured":"T. Gagie , G. Navarro , and N. Prezza . 2018b. Optimal-time text indexing in BWT-runs bounded space . In Proc. 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 1459--1477 . T. Gagie, G. Navarro, and N. Prezza. 2018b. Optimal-time text indexing in BWT-runs bounded space. In Proc. 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 1459--1477."},{"key":"e_1_2_1_49_1","volume-title":"Proc. 13th International Symposium on Experimental Algorithms (SEA). 326--337","author":"Gog S.","unstructured":"S. Gog , T. Beller , A. Moffat , and M. Petri . 2014. From theory to practice: Plug and play with succinct data structures . In Proc. 13th International Symposium on Experimental Algorithms (SEA). 326--337 . S. Gog, T. Beller, A. Moffat, and M. Petri. 2014. From theory to practice: Plug and play with succinct data structures. In Proc. 13th International Symposium on Experimental Algorithms (SEA). 326--337."},{"key":"e_1_2_1_50_1","doi-asserted-by":"crossref","unstructured":"S. Gog and E. Ohlebusch. 2013. Compressed suffix trees: Efficient computation and storage of LCP-values. ACM Journal of Experimental Algorithmics 18 (2013) article 2.1.  S. Gog and E. Ohlebusch. 2013. Compressed suffix trees: Efficient computation and storage of LCP-values. ACM Journal of Experimental Algorithmics 18 (2013) article 2.1.","DOI":"10.1145\/2444016.2461327"},{"key":"e_1_2_1_51_1","volume-title":"Proc. 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 368--373","author":"Golynski A.","unstructured":"A. Golynski , J. I. Munro , and S. S. Rao . 2006. Rank\/select operations on large alphabets: A tool for text indexing . In Proc. 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 368--373 . A. Golynski, J. I. Munro, and S. S. Rao. 2006. Rank\/select operations on large alphabets: A tool for text indexing. In Proc. 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 368--373."},{"key":"e_1_2_1_52_1","volume-title":"Proc. 18th Annual Symposium on Combinatorial Pattern Matching (CPM). 216--227","author":"Gonz\u00e1lez R.","unstructured":"R. Gonz\u00e1lez and G. Navarro . 2007. Compressed text indexes with fast locate . In Proc. 18th Annual Symposium on Combinatorial Pattern Matching (CPM). 216--227 . R. Gonz\u00e1lez and G. Navarro. 2007. Compressed text indexes with fast locate. In Proc. 18th Annual Symposium on Combinatorial Pattern Matching (CPM). 216--227."},{"key":"e_1_2_1_53_1","article-title":"Locally compressed suffix arrays","volume":"19","author":"Gonz\u00e1lez R.","year":"2014","unstructured":"R. Gonz\u00e1lez , G. Navarro , and H. Ferrada . 2014 . Locally compressed suffix arrays . ACM Journal of Experimental Algorithmics 19 , 1 (2014), article 1. R. Gonz\u00e1lez, G. Navarro, and H. Ferrada. 2014. Locally compressed suffix arrays. ACM Journal of Experimental Algorithmics 19, 1 (2014), article 1.","journal-title":"ACM Journal of Experimental Algorithmics"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702402354"},{"key":"e_1_2_1_55_1","volume-title":"Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology","author":"Gusfield D.","unstructured":"D. Gusfield . 1997. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology . Cambridge University Press . D. Gusfield. 1997. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. Cambridge University Press."},{"key":"e_1_2_1_56_1","volume-title":"Tail bounds for sums of geometric and exponential variables. CoRR 1709.08157v1","author":"Janson S.","year":"2017","unstructured":"S. Janson . 2017. Tail bounds for sums of geometric and exponential variables. CoRR 1709.08157v1 ( 2017 ). S. Janson. 2017. Tail bounds for sums of geometric and exponential variables. CoRR 1709.08157v1 (2017)."},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.05.027"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.12.032"},{"key":"e_1_2_1_59_1","volume-title":"Proc. 24th Annual Symposium on Combinatorial Pattern Matching (CPM). 189--200","author":"K\u00e4rkk\u00e4inen J.","unstructured":"J. K\u00e4rkk\u00e4inen , D. Kempa , and S. J. Puglisi . 2013. Linear time Lempel-Ziv factorization: Simple, fast, small . In Proc. 24th Annual Symposium on Combinatorial Pattern Matching (CPM). 189--200 . J. K\u00e4rkk\u00e4inen, D. Kempa, and S. J. Puglisi. 2013. Linear time Lempel-Ziv factorization: Simple, fast, small. In Proc. 24th Annual Symposium on Combinatorial Pattern Matching (CPM). 189--200."},{"key":"e_1_2_1_60_1","volume-title":"Proc. 20th Annual Symposium on Combinatorial Pattern Matching (CPM). 181--192","author":"K\u00e4rkk\u00e4inen J.","unstructured":"J. K\u00e4rkk\u00e4inen , G. Manzini , and S. J. Puglisi . 2009. Permuted longest-common-prefix array . In Proc. 20th Annual Symposium on Combinatorial Pattern Matching (CPM). 181--192 . J. K\u00e4rkk\u00e4inen, G. Manzini, and S. J. Puglisi. 2009. Permuted longest-common-prefix array. In Proc. 20th Annual Symposium on Combinatorial Pattern Matching (CPM). 181--192."},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/1217856.1217858"},{"key":"e_1_2_1_62_1","volume-title":"Proc. 12th Annual Symposium on Combinatorial Pattern Matching (CPM). 181--192","author":"Kasai T.","unstructured":"T. Kasai , G. Lee , H. Arimura , S. Arikawa , and K. Park . 2001. Linear-time longest-common-prefix computation in suffix arrays and its applications . In Proc. 12th Annual Symposium on Combinatorial Pattern Matching (CPM). 181--192 . T. Kasai, G. Lee, H. Arimura, S. Arikawa, and K. Park. 2001. Linear-time longest-common-prefix computation in suffix arrays and its applications. In Proc. 12th Annual Symposium on Combinatorial Pattern Matching (CPM). 181--192."},{"key":"e_1_2_1_63_1","doi-asserted-by":"crossref","unstructured":"B. N. Keel and W. M. Snelling. 2018. Comparison of Burrows-Wheeler transform-based mapping algorithms used in high-throughput whole-genome sequencing: Application to Illumina data for livestock genomes. Frontiers in Genetics 9 (2018) article 35.  B. N. Keel and W. M. Snelling. 2018. Comparison of Burrows-Wheeler transform-based mapping algorithms used in high-throughput whole-genome sequencing: Application to Illumina data for livestock genomes. Frontiers in Genetics 9 (2018) article 35.","DOI":"10.3389\/fgene.2018.00035"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.82"},{"key":"e_1_2_1_65_1","unstructured":"D. Kempa and T. Kociumaka. 2019. Resolution of the Burrows-Wheeler transform conjecture. CoRR 1910.10631 (2019).  D. Kempa and T. Kociumaka. 2019. Resolution of the Burrows-Wheeler transform conjecture. CoRR 1910.10631 (2019)."},{"key":"e_1_2_1_66_1","volume-title":"Proc. 50th Annual ACM Symposium on the Theory of Computing (STOC). 827--840","author":"Kempa D.","unstructured":"D. Kempa and N. Prezza . 2018. At the roots of dictionary compression: String attractors . In Proc. 50th Annual ACM Symposium on the Theory of Computing (STOC). 827--840 . D. Kempa and N. Prezza. 2018. At the roots of dictionary compression: String attractors. In Proc. 50th Annual ACM Symposium on the Theory of Computing (STOC). 827--840."},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.841160"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2004.08.019"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2004.08.002"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1093\/nar\/gkr854"},{"key":"e_1_2_1_71_1","volume-title":"Proc. 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 565--574","author":"Kopelowitz T.","unstructured":"T. Kopelowitz and M. Lewenstein . 2007. Dynamic weighted ancestors . In Proc. 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 565--574 . T. Kopelowitz and M. Lewenstein. 2007. Dynamic weighted ancestors. In Proc. 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 565--574."},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.02.006"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-17083-7_10"},{"key":"e_1_2_1_74_1","volume-title":"Proc. 17th International Symposium on String Processing and Information Retrieval (SPIRE). 201--206","author":"Kuruppu S.","unstructured":"S. Kuruppu , S. J. Puglisi , and J. Zobel . 2010. Relative Lempel-Ziv compression of genomes for large-scale storage and retrieval . In Proc. 17th International Symposium on String Processing and Information Retrieval (SPIRE). 201--206 . S. Kuruppu, S. J. Puglisi, and J. Zobel. 2010. Relative Lempel-Ziv compression of genomes for large-scale storage and retrieval. In Proc. 17th International Symposium on String Processing and Information Retrieval (SPIRE). 201--206."},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1038\/nmeth.1923"},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1186\/gb-2009-10-3-r25"},{"key":"e_1_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1109\/5.892708"},{"key":"e_1_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1976.1055501"},{"key":"e_1_2_1_79_1","doi-asserted-by":"crossref","unstructured":"V. M\u00e4kinen D. Belazzougui F. Cunial and A. I. Tomescu. 2015. Genome-Scale Algorithm Design. Cambridge University Press.  V. M\u00e4kinen D. Belazzougui F. Cunial and A. I. Tomescu. 2015. Genome-Scale Algorithm Design. Cambridge University Press.","DOI":"10.1017\/CBO9781139940023"},{"key":"e_1_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.5555\/1195881.1195885"},{"key":"e_1_2_1_81_1","volume-title":"Proc. 13th Annual International Conference on Computational Molecular Biology (RECOMB). 121--137","author":"M\u00e4kinen V.","unstructured":"V. M\u00e4kinen , G. Navarro , J. Sir\u00e9n , and N. V\u00e4lim\u00e4ki . 2009. Storage and retrieval of individual genomes . In Proc. 13th Annual International Conference on Computational Molecular Biology (RECOMB). 121--137 . V. M\u00e4kinen, G. Navarro, J. Sir\u00e9n, and N. V\u00e4lim\u00e4ki. 2009. Storage and retrieval of individual genomes. In Proc. 13th Annual International Conference on Computational Molecular Biology (RECOMB). 121--137."},{"key":"e_1_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.1089\/cmb.2009.0169"},{"key":"e_1_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222058"},{"key":"e_1_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.1145\/382780.382782"},{"key":"e_1_2_1_85_1","doi-asserted-by":"publisher","DOI":"10.1145\/321941.321946"},{"key":"e_1_2_1_86_1","volume-title":"Proc. 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 408--424","author":"Munro J. I.","unstructured":"J. I. Munro , G. Navarro , and Y. Nekrich . 2017. Space-efficient construction of compressed indexes in deterministic linear time . In Proc. 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 408--424 . J. I. Munro, G. Navarro, and Y. Nekrich. 2017. Space-efficient construction of compressed indexes in deterministic linear time. In Proc. 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 408--424."},{"key":"e_1_2_1_87_1","volume-title":"Proc. 24th International Workshop on Combinatorial Algorithms (IWOCA). 337--348","author":"Na J. C.","unstructured":"J. C. Na , H. Park , M. Crochemore , J. Holub , C. S. Iliopoulos , L. Mouchard , and K. Park . 2013a. Suffix tree of alignment: An efficient index for similar data . In Proc. 24th International Workshop on Combinatorial Algorithms (IWOCA). 337--348 . J. C. Na, H. Park, M. Crochemore, J. Holub, C. S. Iliopoulos, L. Mouchard, and K. Park. 2013a. Suffix tree of alignment: An efficient index for similar data. In Proc. 24th International Workshop on Combinatorial Algorithms (IWOCA). 337--348."},{"key":"e_1_2_1_88_1","volume-title":"Proc. 20th International Symposium on String Processing and Information Retrieval (SPIRE). 243--254","author":"Na J. C.","unstructured":"J. C. Na , H. Park , S. Lee , M. Hong , T. Lecroq , L. Mouchard , and K. Park . 2013b. Suffix array of alignment: A practical index for similar data . In Proc. 20th International Symposium on String Processing and Information Retrieval (SPIRE). 243--254 . J. C. Na, H. Park, S. Lee, M. Hong, T. Lecroq, L. Mouchard, and K. Park. 2013b. Suffix array of alignment: A practical index for similar data. In Proc. 20th International Symposium on String Processing and Information Retrieval (SPIRE). 243--254."},{"key":"e_1_2_1_89_1","volume-title":"Compact Data Structures -- A Practical Approach","author":"Navarro Gonzalo","unstructured":"Gonzalo Navarro . 2016. Compact Data Structures -- A Practical Approach . Cambridge University Press . Gonzalo Navarro. 2016. Compact Data Structures -- A Practical Approach. Cambridge University Press."},{"key":"e_1_2_1_90_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-67428-5_24"},{"key":"e_1_2_1_91_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2018.11.022"},{"key":"e_1_2_1_92_1","doi-asserted-by":"crossref","unstructured":"G. Navarro and V. M\u00e4kinen. 2007. Compressed full-text indexes. Comput. Surveys 39 1 (2007) article 2.  G. Navarro and V. M\u00e4kinen. 2007. Compressed full-text indexes. Comput. Surveys 39 1 (2007) article 2.","DOI":"10.1145\/1216370.1216372"},{"key":"e_1_2_1_93_1","doi-asserted-by":"publisher","DOI":"10.1137\/140998949"},{"key":"e_1_2_1_94_1","doi-asserted-by":"publisher","DOI":"10.1145\/2851495"},{"key":"e_1_2_1_95_1","unstructured":"G. Navarro and N. Prezza. 2018. On the approximation ratio of greedy parsings. CoRR 1803.09517 (2018).  G. Navarro and N. Prezza. 2018. On the approximation ratio of greedy parsings. CoRR 1803.09517 (2018)."},{"key":"e_1_2_1_96_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2018.09.007"},{"key":"e_1_2_1_97_1","doi-asserted-by":"publisher","DOI":"10.1145\/2601073"},{"key":"e_1_2_1_98_1","unstructured":"T. Nishimoto T. I S. Inenaga H. Bannai and M. Takeda. 2015. Dynamic index LZ factorization and LCE queries in compressed space. CoRR 1504.06954 (2015).  T. Nishimoto T. I S. Inenaga H. Bannai and M. Takeda. 2015. Dynamic index LZ factorization and LCE queries in compressed space. CoRR 1504.06954 (2015)."},{"key":"e_1_2_1_99_1","volume-title":"Proc. 41st International Symposium on Mathematical Foundations of Computer Science (MFCS). 72:1--72:15","author":"Nishimoto T.","unstructured":"T. Nishimoto , T. I, S. Inenaga , H. Bannai , and M. Takeda . 2016. Fully dynamic data structure for LCE queries in compressed space . In Proc. 41st International Symposium on Mathematical Foundations of Computer Science (MFCS). 72:1--72:15 . T. Nishimoto, T. I, S. Inenaga, H. Bannai, and M. Takeda. 2016. Fully dynamic data structure for LCE queries in compressed space. In Proc. 41st International Symposium on Mathematical Foundations of Computer Science (MFCS). 72:1--72:15."},{"key":"e_1_2_1_100_1","volume-title":"Genome Rearrangements, and Phylogenetic Reconstruction","author":"Ohlebusch E.","unstructured":"E. Ohlebusch . 2013. Bioinformatics Algorithms: Sequence Analysis , Genome Rearrangements, and Phylogenetic Reconstruction . Oldenbusch Verlag . E. Ohlebusch. 2013. Bioinformatics Algorithms: Sequence Analysis, Genome Rearrangements, and Phylogenetic Reconstruction. Oldenbusch Verlag."},{"key":"e_1_2_1_101_1","doi-asserted-by":"crossref","unstructured":"T. Ohno K. Sakai Y. Takabatake T. I and H. Sakamoto. 2018. A faster implementation of online RLBWT and its application to LZ77 parsing. Journal of Discrete Algorithms 52--53 (2018) 18--28.  T. Ohno K. Sakai Y. Takabatake T. I and H. Sakamoto. 2018. A faster implementation of online RLBWT and its application to LZ77 parsing. Journal of Discrete Algorithms 52--53 (2018) 18--28.","DOI":"10.1016\/j.jda.2018.11.002"},{"key":"e_1_2_1_102_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-017-0327-z"},{"key":"e_1_2_1_104_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0168-9525(00)02030-8"},{"key":"e_1_2_1_105_1","doi-asserted-by":"publisher","DOI":"10.1145\/1290672.1290680"},{"key":"e_1_2_1_106_1","doi-asserted-by":"publisher","DOI":"10.1145\/2000807.2000821"},{"key":"e_1_2_1_107_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70575-8_8"},{"key":"e_1_2_1_108_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(02)00777-6"},{"key":"e_1_2_1_109_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-006-1198-x"},{"key":"e_1_2_1_110_1","doi-asserted-by":"publisher","DOI":"10.1109\/MSPEC.2013.6545119"},{"key":"e_1_2_1_111_1","volume-title":"Proc. 15th International Symposium on String Processing and Information Retrieval (SPIRE). 164--175","author":"Sir\u00e9n J.","unstructured":"J. Sir\u00e9n , N. V\u00e4lim\u00e4ki , V. M\u00e4kinen , and G. Navarro . 2008. Run-length compressed indexes are superior for highly repetitive sequence collections . In Proc. 15th International Symposium on String Processing and Information Retrieval (SPIRE). 164--175 . J. Sir\u00e9n, N. V\u00e4lim\u00e4ki, V. M\u00e4kinen, and G. Navarro. 2008. Run-length compressed indexes are superior for highly repetitive sequence collections. In Proc. 15th International Symposium on String Processing and Information Retrieval (SPIRE). 164--175."},{"key":"e_1_2_1_112_1","doi-asserted-by":"crossref","unstructured":"Z. D. Sthephens S. Y. Lee F. Faghri R. H. Campbell Z. Chenxiang M. J. Efron R. Iyer S. Sinha and G. E. Robinson. 2015. Big data: Astronomical or genomical?PLoS Biology 17 7 (2015) e1002195.  Z. D. Sthephens S. Y. Lee F. Faghri R. H. Campbell Z. Chenxiang M. J. Efron R. Iyer S. Sinha and G. E. Robinson. 2015. Big data: Astronomical or genomical?PLoS Biology 17 7 (2015) e1002195.","DOI":"10.1371\/journal.pbio.1002195"},{"key":"e_1_2_1_113_1","doi-asserted-by":"publisher","DOI":"10.1145\/322344.322346"},{"key":"e_1_2_1_114_1","volume-title":"Proc. 24th International Symposium of String Processing and Information Retrieval (SPIRE). 304--316","author":"Takagi T.","unstructured":"T. Takagi , K. Goto , Y. Fujishige , S. Inenaga , and H. Arimura . 2017. Linear-size CDAWG: New repetition-aware indexing and grammar compression . In Proc. 24th International Symposium of String Processing and Information Retrieval (SPIRE). 304--316 . T. Takagi, K. Goto, Y. Fujishige, S. Inenaga, and H. Arimura. 2017. Linear-size CDAWG: New repetition-aware indexing and grammar compression. In Proc. 24th International Symposium of String Processing and Information Retrieval (SPIRE). 304--316."},{"key":"e_1_2_1_115_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01206331"},{"key":"e_1_2_1_116_1","volume-title":"Proc. 24th Annual Symposium on Combinatorial Pattern Matching (CPM). 247--258","author":"Verbin E.","unstructured":"E. Verbin and W. Yu . 2013. Data structure lower bounds on random access to grammar-compressed strings . In Proc. 24th Annual Symposium on Combinatorial Pattern Matching (CPM). 247--258 . E. Verbin and W. Yu. 2013. Data structure lower bounds on random access to grammar-compressed strings. In Proc. 24th Annual Symposium on Combinatorial Pattern Matching (CPM). 247--258."},{"key":"e_1_2_1_117_1","doi-asserted-by":"publisher","DOI":"10.1109\/SWAT.1973.13"},{"key":"e_1_2_1_118_1","doi-asserted-by":"publisher","DOI":"10.5555\/337729.337809"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3375890","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3375890","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:38:15Z","timestamp":1750199895000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3375890"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,1,15]]},"references-count":117,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,2,29]]}},"alternative-id":["10.1145\/3375890"],"URL":"https:\/\/doi.org\/10.1145\/3375890","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,1,15]]},"assertion":[{"value":"2018-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2019-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-01-15","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}