{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T13:36:38Z","timestamp":1770903398990,"version":"3.50.1"},"reference-count":72,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2020,3,9]],"date-time":"2020-03-09T00:00:00Z","timestamp":1583712000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100002341","name":"Academy of Finland","doi-asserted-by":"crossref","award":["250345, 284598, and 309048"],"award-info":[{"award-number":["250345, 284598, and 309048"]}],"id":[{"id":"10.13039\/501100002341","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2020,4,30]]},"abstract":"<jats:p>\n            The field of\n            <jats:italic>succinct data structures<\/jats:italic>\n            has flourished over the past 16 years. Starting from the compressed suffix array by Grossi and Vitter (STOC 2000) and the FM-index by Ferragina and Manzini (FOCS 2000), a number of generalizations and applications of string indexes based on the Burrows-Wheeler transform (BWT) have been developed, all taking an amount of space that is close to the input size in bits. In many large-scale applications, the construction of the index and its usage need to be considered as one unit of computation. For example, one can compare two genomes by building a common index for their concatenation and by detecting common substructures by querying the index. Efficient string indexing and analysis in small space lies also at the core of a number of primitives in the data-intensive field of high-throughput DNA sequencing.\n          <\/jats:p>\n          <jats:p>\n            We report the following advances in string indexing and analysis: We show that the BWT of a string\n            <jats:italic>T<\/jats:italic>\n            \u2208 {1,\u2026,\u03c3}\n            <jats:sup>\n              <jats:italic>n<\/jats:italic>\n            <\/jats:sup>\n            can be built in deterministic\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ) time using just\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            log \u03c3) bits of space, where \u03c3 \u2264\n            <jats:italic>n<\/jats:italic>\n            . Deterministic linear time is achieved by exploiting a new\n            <jats:italic>partial rank<\/jats:italic>\n            data structure that supports queries in constant time and that might have independent interest. Within the same time and space budget, we can build an index based on the BWT that allows one to enumerate all the internal nodes of the suffix tree of\n            <jats:italic>T<\/jats:italic>\n            . Many fundamental string analysis problems, such as maximal repeats, maximal unique matches, and string kernels, can be mapped to such enumeration and can thus be solved in deterministic\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ) time and in\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            log \u03c3) bits of space from the input string by tailoring the enumeration algorithm to some problem-specific computations.\n          <\/jats:p>\n          <jats:p>\n            We also show how to build many of the existing indexes based on the BWT, such as the\n            <jats:italic>compressed suffix array<\/jats:italic>\n            , the\n            <jats:italic>compressed suffix tree<\/jats:italic>\n            , and the\n            <jats:italic>bidirectional BWT index<\/jats:italic>\n            , in\n            <jats:italic>randomized<\/jats:italic>\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            ) time and in\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            log \u03c3) bits of space. The previously fastest construction algorithms for BWT, compressed suffix array and compressed suffix tree, which used\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            log \u03c3) bits of space, took\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            log log \u03c3) time for the first two structures and\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            log\n            <jats:sup>\u03f5<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ) time for the third, where \u03f5 is any positive constant smaller than one. Alternatively, the BWT could be previously built in linear time if one was willing to spend\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            log \u03c3 log log\n            <jats:sub>\u03c3<\/jats:sub>\n            <jats:italic>n<\/jats:italic>\n            ) bits of space. Contrary to the state-of-the-art, our bidirectional BWT index supports every operation in constant time per element in its output.\n          <\/jats:p>","DOI":"10.1145\/3381417","type":"journal-article","created":{"date-parts":[[2020,3,9]],"date-time":"2020-03-09T21:33:40Z","timestamp":1583789620000},"page":"1-54","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":20,"title":["Linear-time String Indexing and Analysis in Small Space"],"prefix":"10.1145","volume":"16","author":[{"given":"Djamal","family":"Belazzougui","sequence":"first","affiliation":[{"name":"University of Helsinki, Helsinki, Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fabio","family":"Cunial","sequence":"additional","affiliation":[{"name":"University of Helsinki, Helsinki, Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Juha","family":"K\u00e4rkk\u00e4inen","sequence":"additional","affiliation":[{"name":"University of Helsinki, Helsinki, Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Veli","family":"M\u00e4kinen","sequence":"additional","affiliation":[{"name":"University of Helsinki, Helsinki, Finland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,3,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1240233.1240242"},{"key":"e_1_2_1_2_1","volume-title":"Combinatorial Algorithms on Words (NATO ISI Series)","author":"Apostolico Alberto","unstructured":"Alberto Apostolico . 1985. The myriad virtues of subword trees . In Combinatorial Algorithms on Words (NATO ISI Series) . Springer-Verlag , 85--96. Alberto Apostolico. 1985. The myriad virtues of subword trees. In Combinatorial Algorithms on Words (NATO ISI Series). Springer-Verlag, 85--96."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/WCRE.1995.514697"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1186\/s12859-014-0388-9"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591885"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973068.86"},{"key":"e_1_2_1_7_1","first-page":"3","article-title":"Theory and practice of monotone minimal perfect hashing","volume":"16","author":"Belazzougui Djamal","year":"2011","unstructured":"Djamal Belazzougui , Paolo Boldi , Rasmus Pagh , and Sebastiano Vigna . 2011 . Theory and practice of monotone minimal perfect hashing . J. Exper. Algor. 16 (2011), 3 -- 2 . Djamal Belazzougui, Paolo Boldi, Rasmus Pagh, and Sebastiano Vigna. 2011. Theory and practice of monotone minimal perfect hashing. J. Exper. Algor. 16 (2011), 3--2.","journal-title":"J. Exper. Algor."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-11918-2_18"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-017-0286-4"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 30th Symposium on Combinatorial Pattern Matching (CPM\u201919)","author":"Belazzougui Djamal","year":"2019","unstructured":"Djamal Belazzougui and Fabio Cunial . 2019 . Fully-functional bidirectional Burrows-Wheeler indexes and infinite-order de Bruijn graphs . In Proceedings of the 30th Symposium on Combinatorial Pattern Matching (CPM\u201919) . Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Djamal Belazzougui and Fabio Cunial. 2019. Fully-functional bidirectional Burrows-Wheeler indexes and infinite-order de Bruijn graphs. In Proceedings of the 30th Symposium on Combinatorial Pattern Matching (CPM\u201919). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_2_1_11_1","article-title":"Alphabet-independent compressed text indexing","volume":"10","author":"Belazzougui Djamal","year":"2014","unstructured":"Djamal Belazzougui and Gonzalo Navarro . 2014 . Alphabet-independent compressed text indexing . ACM Trans. Algor. 10 , 4 (2014), 23:1--23:19. Djamal Belazzougui and Gonzalo Navarro. 2014. Alphabet-independent compressed text indexing. ACM Trans. Algor. 10, 4 (2014), 23:1--23:19.","journal-title":"ACM Trans. Algor."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2012.07.005"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-34109-0_11"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2012.07.007"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 2nd Electrotechnical and Computer Science Conference","volume":"90","author":"Brodnik Andrej","year":"1993","unstructured":"Andrej Brodnik . 1993 . Computation of the least significant set bit . In Proceedings of the 2nd Electrotechnical and Computer Science Conference , Vol. 90 . Andrej Brodnik. 1993. Computation of the least significant set bit. In Proceedings of the 2nd Electrotechnical and Computer Science Conference, Vol. 90."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2015.01.004"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(98)00104-5"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/321812.321820"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1975.1055349"},{"key":"e_1_2_1_22_1","volume-title":"On the Number of Bits Required to Implement an Associative Memory","author":"Fano Robert M.","unstructured":"Robert M. Fano . 1971. On the Number of Bits Required to Implement an Associative Memory . Computer Structures Group , Project MAC, MIT, Cambridge, MA. Robert M. Fano. 1971. On the Number of Bits Required to Implement an Associative Memory. Computer Structures Group, Project MAC, MIT, Cambridge, MA."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1997.646102"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2000.892127"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1082036.1082039"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.12.012"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-12200-2_16"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.01.036"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201906)","author":"Golynski Alexander","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 ACM-SIAM Symposium on Discrete Algorithms (SODA\u201906) . ACM, 368--373. 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 ACM-SIAM Symposium on Discrete Algorithms (SODA\u201906). ACM, 368--373."},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201903)","author":"Grossi Roberto","year":"2003","unstructured":"Roberto Grossi , Ankur Gupta , and Jeffrey Scott Vitter . 2003 . High-order entropy-compressed text indexes . In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201903) . SIAM, 841--850. Roberto Grossi, Ankur Gupta, and Jeffrey Scott Vitter. 2003. High-order entropy-compressed text indexes. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201903). SIAM, 841--850."},{"key":"e_1_2_1_31_1","unstructured":"Roberto Grossi Alessio Orlandi Rajeev Raman and S. Srinivasa Rao. 2009. More haste less waste: Lowering the redundancy in fully indexable dictionaries. arXiv preprint arXiv:0902.2648.  Roberto Grossi Alessio Orlandi Rajeev Raman and S. Srinivasa Rao. 2009. More haste less waste: Lowering the redundancy in fully indexable dictionaries. arXiv preprint arXiv:0902.2648."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702402354"},{"key":"e_1_2_1_33_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 , Cambridge, UK . D. Gusfield. 1997. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. Cambridge University Press, Cambridge, UK."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2001.1171"},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS\u201901)","author":"Hagerup T.","unstructured":"T. Hagerup and T. Tholey . 2001. Efficient minimal perfect hashing in nearly minimal space . In Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS\u201901) . Springer-Verlag, 317--326. T. Hagerup and T. Tholey. 2001. Efficient minimal perfect hashing in nearly minimal space. In Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS\u201901). Springer-Verlag, 317--326."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/5.1.10"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45452-7_13"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/070685373"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1217856.1217858"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.82"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316368"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2004.08.019"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44888-8_15"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2011.127"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/BIBM.2009.42"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btp336"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1162\/153244302760200687"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222058"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/382780.382782"},{"key":"e_1_2_1_51_1","volume-title":"Tables. In Proceedings of the 16th Conference on Foundations of Software Technology and Theoretical Computer Science (LNCS)","volume":"1180","author":"Munro I.","year":"1996","unstructured":"I. Munro . 1996 . Tables. In Proceedings of the 16th Conference on Foundations of Software Technology and Theoretical Computer Science (LNCS) , Vol. 1180 . Springer, 37--42. I. Munro. 1996. Tables. In Proceedings of the 16th Conference on Foundations of Software Technology and Theoretical Computer Science (LNCS), Vol. 1180. Springer, 37--42."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.26"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45061-0_29"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799364092"},{"key":"e_1_2_1_55_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201902)","author":"Muthukrishnan S.","year":"2002","unstructured":"S. Muthukrishnan . 2002 . Efficient algorithms for document retrieval problems . In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201902) . ACM-SIAM, 657--666. S. Muthukrishnan. 2002. Efficient algorithms for document retrieval problems. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201902). ACM-SIAM, 657--666."},{"key":"e_1_2_1_56_1","doi-asserted-by":"crossref","unstructured":"G. Navarro and V. M\u00e4kinen. 2007. Compressed full-text indexes. Comput. Surv. 39 1 (2007) Article 2.  G. Navarro and V. M\u00e4kinen. 2007. Compressed full-text indexes. Comput. Surv. 39 1 (2007) Article 2.","DOI":"10.1145\/1216370.1216372"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1137\/130908245"},{"key":"e_1_2_1_58_1","article-title":"Fully functional static and dynamic succinct trees","volume":"10","author":"Navarro Gonzalo","year":"2014","unstructured":"Gonzalo Navarro and Kunihiko Sadakane . 2014 . Fully functional static and dynamic succinct trees . ACM Trans. Algor. 10 , 3 (2014), 16:1--16:39. Gonzalo Navarro and Kunihiko Sadakane. 2014. Fully functional static and dynamic succinct trees. ACM Trans. Algor. 10, 3 (2014), 16:1--16:39.","journal-title":"ACM Trans. Algor."},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2013.06.002"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972870.6"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03784-9_9"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972795.72"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700369909"},{"key":"e_1_2_1_64_1","volume-title":"Succincter. In Proceedings of the 49th IEEE Symposium on Foundations of Computer Science (FOCS\u201908)","author":"Patrascu Mihai","year":"2008","unstructured":"Mihai Patrascu . 2008 . Succincter. In Proceedings of the 49th IEEE Symposium on Foundations of Computer Science (FOCS\u201908) . IEEE, 305--313. Mihai Patrascu. 2008. Succincter. In Proceedings of the 49th IEEE Symposium on Foundations of Computer Science (FOCS\u201908). IEEE, 305--313."},{"key":"e_1_2_1_65_1","volume-title":"Proceedings of the 30th Symposium on Combinatorial Pattern Matching (CPM\u201919)","author":"Prezza Nicola","year":"2019","unstructured":"Nicola Prezza and Giovanna Rosone . 2019 . Space-efficient computation of the LCP array from the Burrows-Wheeler transform . In Proceedings of the 30th Symposium on Combinatorial Pattern Matching (CPM\u201919) . Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Nicola Prezza and Giovanna Rosone. 2019. Space-efficient computation of the LCP array from the Burrows-Wheeler transform. In Proceedings of the 30th Symposium on Combinatorial Pattern Matching (CPM\u201919). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_2_1_66_1","first-page":"37","article-title":"A generalization of quasi-monotone sequences. Proc. Edinburgh","volume":"16","author":"Robertson M. M.","year":"1968","unstructured":"M. M. Robertson . 1968 . A generalization of quasi-monotone sequences. Proc. Edinburgh Math. Soc. (Series 2) 16 , 01 (1968), 37 -- 41 . M. M. Robertson. 1968. A generalization of quasi-monotone sequences. Proc. Edinburgh Math. Soc. (Series 2) 16, 01 (1968), 37--41.","journal-title":"Math. Soc. (Series 2)"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-40996-3_35"},{"key":"e_1_2_1_68_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201902)","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 ACM-SIAM Symposium on Discrete Algorithms (SODA\u201902) . ACM-SIAM, 225--232. Kunihiko Sadakane. 2002. Succinct representations of LCP information and improvements in the compressed suffix arrays. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA\u201902). ACM-SIAM, 225--232."},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-006-1198-x"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2006.03.011"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973075.13"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2011.03.007"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1145\/1499586.1499701"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1109\/SWAT.1973.13"},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(83)90075-3"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3381417","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3381417","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:33:06Z","timestamp":1750199586000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3381417"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,3,9]]},"references-count":72,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,4,30]]}},"alternative-id":["10.1145\/3381417"],"URL":"https:\/\/doi.org\/10.1145\/3381417","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,3,9]]},"assertion":[{"value":"2018-10-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-03-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}