乐胖代购免代理版

{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,6,20]],"date-time":"2024-06-20T22:33:39Z","timestamp":1718922819435},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"6","funder":[{"DOI":"10.13039\/501100001824","name":"Grant Agency of the Czech Republic","doi-asserted-by":"crossref","award":["19-27871X"],"id":[{"id":"10.13039\/501100001824","id-type":"DOI","asserted-by":"crossref"}]},{"name":"European Research Council","award":["616787"]},{"DOI":"10.13039\/100000893","name":"Simons Foundation","doi-asserted-by":"crossref","award":["332622"],"id":[{"id":"10.13039\/100000893","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2020,12,31]]},"abstract":"\n Edit distance is a measure of similarity of two strings based on the minimum number of character insertions, deletions, and substitutions required to transform one string into the other. The edit distance can be computed exactly using a dynamic programming algorithm that runs in quadratic time. Andoni, Krauthgamer, and Onak (2010) gave a nearly linear time algorithm that approximates edit distance within approximation factor poly(log\n n<\/jats:italic>\n ).\n <\/jats:p>\n \n In this article, we provide an algorithm with running time \u00d5(\n n<\/jats:italic>\n 2\u22122\/7<\/jats:sup>\n ) that approximates the edit distance within a constant factor.\n <\/jats:p>","DOI":"10.1145\/3422823","type":"journal-article","created":{"date-parts":[[2020,10,29]],"date-time":"2020-10-29T10:05:36Z","timestamp":1603965936000},"page":"1-22","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Approximating Edit Distance Within Constant Factor in Truly Sub-quadratic Time"],"prefix":"10.1145","volume":"67","author":[{"ORCID":"http:\/\/orcid.org\/0000-0002-0687-5823","authenticated-orcid":false,"given":"Diptarka","family":"Chakraborty","sequence":"first","affiliation":[{"name":"School of Computing, National University of Singapore, Singapore"}]},{"given":"Debarati","family":"Das","sequence":"additional","affiliation":[{"name":"University of Copenhagen, Denmark"}]},{"given":"Elazar","family":"Goldenberg","sequence":"additional","affiliation":[{"name":"The Academic College of Tel-Aviv-Yaffo, Yaffo, Israel"}]},{"given":"Michal","family":"Kouck\u00fd","sequence":"additional","affiliation":[{"name":"Charles University, Prague, Czech Republic"}]},{"given":"Michael","family":"Saks","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Rutgers University, Piscataway, NJ, USA"}]}],"member":"320","published-online":{"date-parts":[[2020,10,29]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 8th Innovations in Theoretical Computer Science Conference (ITCS\u201917)","author":"Abboud Amir","year":"2017","unstructured":"Amir Abboud and Arturs Backurs . 2017 . Towards hardness of approximation for polynomial time problems . In Proceedings of the 8th Innovations in Theoretical Computer Science Conference (ITCS\u201917) . 11:1--11:26. Amir Abboud and Arturs Backurs. 2017. Towards hardness of approximation for polynomial time problems. In Proceedings of the 8th Innovations in Theoretical Computer Science Conference (ITCS\u201917). 11:1--11:26."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.14"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897653"},{"key":"e_1_2_1_4_1","unstructured":"Alexandr Andoni. 2018. Simpler constant-factor approximation to edit distance problems. Alexandr Andoni. 2018. Simpler constant-factor approximation to edit distance problems."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.43"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201910)","author":"Andoni Alexandr","year":"1973","unstructured":"Alexandr Andoni and Huy L. Nguyen . 2010. Near-optimal sublinear time algorithms for Ulam distance . In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201910) . 76--86. DOI:https:\/\/doi.org\/10.1137\/1.978161 1973 075.8 10.1137\/1.9781611973075.8 Alexandr Andoni and Huy L. Nguyen. 2010. Near-optimal sublinear time algorithms for Ulam distance. In Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201910). 76--86. DOI:https:\/\/doi.org\/10.1137\/1.9781611973075.8"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00096"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536444"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746612"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science. 550--559","author":"Bar-Yossef Z.","unstructured":"Z. Bar-Yossef , T. S. Jayram , R. Krauthgamer , and R. Kumar . 2004. Approximating edit distance efficiently . In Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science. 550--559 . Z. Bar-Yossef, T. S. Jayram, R. Krauthgamer, and R. Kumar. 2004. Approximating edit distance efficiently. In Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science. 550--559."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780590"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1109557.1109644"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201918)","author":"Boroujeni Mahdi","year":"2018","unstructured":"Mahdi Boroujeni , Soheil Ehsani , Mohammad Ghodsi , Mohammad Taghi Hajiaghayi , and Saeed Seddighin . 2018 . Approximating edit distance in truly sub-quadratic time: Quantum and MapReduce . In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201918) . 1170--1189. Mahdi Boroujeni, Soheil Ehsani, Mohammad Ghodsi, Mohammad Taghi Hajiaghayi, and Saeed Seddighin. 2018. Approximating edit distance in truly sub-quadratic time: Quantum and MapReduce. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201918). 1170--1189."},{"key":"e_1_2_1_14_1","volume-title":"Mohammad Taghi Hajiaghayi, and Saeed Seddighin","author":"Boroujeni Mahdi","year":"2018","unstructured":"Mahdi Boroujeni , Soheil Ehsani , Mohammad Ghodsi , Mohammad Taghi Hajiaghayi, and Saeed Seddighin . 2018 . Approximating edit distance in truly sub-quadratic time: Quantum and MapReduce (extended version of Reference [13]). Mahdi Boroujeni, Soheil Ehsani, Mohammad Ghodsi, Mohammad Taghi Hajiaghayi, and Saeed Seddighin. 2018. Approximating edit distance in truly sub-quadratic time: Quantum and MapReduce (extended version of Reference [13])."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384282"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.15"},{"key":"e_1_2_1_17_1","doi-asserted-by":"crossref","unstructured":"Diptarka Chakraborty Elazar Goldenberg and Michal Kouck\u00fd. 2016. Streaming algorithms for computing edit distance without exploiting suffix trees. Retrieved from https:\/\/arxiv:1607.03718. Diptarka Chakraborty Elazar Goldenberg and Michal Kouck\u00fd. 2016. Streaming algorithms for computing edit distance without exploiting suffix trees. Retrieved from https:\/\/arxiv:1607.03718.","DOI":"10.1145\/2897518.2897577"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897577"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2015.10.040"},{"key":"e_1_2_1_20_1","volume-title":"Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC'20)","author":"Kouck\u00fd Michal","unstructured":"Michal Kouck\u00fd and Michael E. Saks . 2020. Constant factor approximations to edit distance on far input pairs in nearly linear time . In Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC'20) . ACM, 699--712. Michal Kouck\u00fd and Michael E. Saks. 2020. Constant factor approximations to edit distance on far input pairs in nearly linear time. In Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC'20). ACM, 699--712."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794264810"},{"key":"e_1_2_1_22_1","first-page":"707","article-title":"Binary codes capable of correcting deletions, insertions and reversals","volume":"10","author":"Levenshtein V. I.","year":"1966","unstructured":"V. I. Levenshtein . 1966 . Binary codes capable of correcting deletions, insertions and reversals . Soviet Physics Doklady 10 (1966), 707 . V. I. Levenshtein. 1966. Binary codes capable of correcting deletions, insertions and reversals. Soviet Physics Doklady 10 (1966), 707.","journal-title":"Soviet Physics Doklady"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(80)90002-1"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201917). 2012","author":"Naumovitz Timothy","year":"2031","unstructured":"Timothy Naumovitz , Michael E. Saks , and C. Seshadhri . 2017. Accurate and nearly optimal sublinear approximations to Ulam distance . In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201917). 2012 -- 2031 . Timothy Naumovitz, Michael E. Saks, and C. Seshadhri. 2017. Accurate and nearly optimal sublinear approximations to Ulam distance. In Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201917). 2012--2031."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.71"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(85)80046-2"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/321796.321811"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3422823","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T18:33:20Z","timestamp":1672598000000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3422823"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,10,29]]},"references-count":27,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2020,12,31]]}},"alternative-id":["10.1145\/3422823"],"URL":"https:\/\/doi.org\/10.1145\/3422823","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,10,29]]},"assertion":[{"value":"2019-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-10-29","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}