{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:33:50Z","timestamp":1759638830070,"version":"3.41.0"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2012,12,1]],"date-time":"2012-12-01T00:00:00Z","timestamp":1354320000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCR-09-04581"],"award-info":[{"award-number":["CCR-09-04581"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["347\/09"],"award-info":[{"award-number":["347\/09"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2012,12]]},"abstract":"<jats:p>\n            Assume that a natural cyclic phenomenon has been measured, but the data is corrupted by errors. The type of corruption is application-dependent and may be caused by measurements errors, or natural features of the phenomenon. We assume that an appropriate metric exists, which measures the amount of corruption experienced. This article studies the problem of recovering the correct cycle from data corrupted by various error models, formally defined as the\n            <jats:italic>period recovery problem<\/jats:italic>\n            . Specifically, we define a metric property which we call\n            <jats:italic>pseudolocality<\/jats:italic>\n            and study the period recovery problem under pseudolocal metrics. Examples of pseudolocal metrics are the Hamming distance, the swap distance, and the interchange (or Cayley) distance. We show that for pseudolocal metrics, periodicity is a powerful property allowing detecting the original cycle and correcting the data, under suitable conditions. Some surprising features of our algorithm are that we can efficiently identify the period in the corrupted data, up to a number of possibilities logarithmic in the length of the data string, even for metrics whose calculation is\n            <jats:italic>NP-hard<\/jats:italic>\n            . For the Hamming metric, we can reconstruct the corrupted data in near-linear time even for unbounded alphabets. This result is achieved using the property of separation in the self-convolution vector and Reed-Solomon codes. Finally, we employ our techniques beyond the scope of pseudo-local metrics and give a recovery algorithm for the non-pseudolocal Levenshtein edit metric.\n          <\/jats:p>","DOI":"10.1145\/2390176.2390189","type":"journal-article","created":{"date-parts":[[2013,1,2]],"date-time":"2013-01-02T13:23:15Z","timestamp":1357132995000},"page":"1-20","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["Cycle detection and correction"],"prefix":"10.1145","volume":"9","author":[{"given":"Amihood","family":"Amir","sequence":"first","affiliation":[{"name":"Bar-Ilan University and Johns Hopkins University, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Estrella","family":"Eisenberg","sequence":"additional","affiliation":[{"name":"Bar-Ilan University, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Avivit","family":"Levy","sequence":"additional","affiliation":[{"name":"Shenkar College and CRI, University of Haifa, Haifa, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ely","family":"Porat","sequence":"additional","affiliation":[{"name":"Bar-Ilan University, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Natalie","family":"Shapira","sequence":"additional","affiliation":[{"name":"Bar-Ilan University, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2012,12,26]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/0216067"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109692"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1120"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795298321"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/165231.165242"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1998.2705"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0890-5401(02)00035-4"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/1778580.1778593"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2006.11.017"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01955046"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/S089548019528280X"},{"volume":"1075","volume-title":"Proceedings of the 8th Annual Symposium on Combinatorial Pattern Matching (CPM), D. Hirschberg and E. Myers, Eds. Lecture Notes in Computer Science","author":"Berman P.","key":"e_1_2_1_12_1"},{"volume-title":"Proceedings of the 29th International Colloquium on Automata, Languages, and Programming (ICALP). 728--739","author":"Brodal G. S.","key":"e_1_2_1_13_1"},{"key":"e_1_2_1_14_1","first-page":"527","article-title":"Note on the theory of permutations","volume":"34","author":"Cayley A.","year":"1849","journal-title":"Philosophical Mag."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(96)00155-X"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1993.366862"},{"key":"e_1_2_1_17_1","unstructured":"Cormen T. H. Leiserson C. E. Rivest R. L. and Stein C. 2001. Introduction to Algorithms 2nd Ed. MIT Press and McGraw-Hill.   Cormen T. H. Leiserson C. E. Rivest R. L. and Stein C. 2001. Introduction to Algorithms 2nd Ed. MIT Press and McGraw-Hill."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(81)90024-7"},{"key":"e_1_2_1_19_1","first-page":"113","article-title":"String matching and other products. Complexity of Computation","volume":"7","author":"Fischer M.","year":"1974","journal-title":"SIAM-AMS Proceedings"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/800057.808687"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539792241941"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(89)90010-2"},{"key":"e_1_2_1_23_1","first-page":"707","article-title":"Binary codes capable of correcting, deletions, insertions and reversals","volume":"10","author":"Levenshtein V. I.","year":"1966","journal-title":"Soviet Phys. Dokl."},{"key":"e_1_2_1_24_1","unstructured":"Lothaire M. 1983. Combinatorics on Words. Addison-Wesley Reading Mass.  Lothaire M. 1983. Combinatorics on Words. Addison-Wesley Reading Mass."},{"volume-title":"Proceedings of the 17th International Conference on Data Engineering (ICDE). IEEE Computer Society, 205--214","author":"Ma S.","key":"e_1_2_1_25_1"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/0108018"},{"volume-title":"Proceedings of the 4th Symposium on Combinatorial Pattern Matching 15","author":"R\u00e9gnier M.","key":"e_1_2_1_27_1"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873704"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2390176.2390189","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2390176.2390189","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:35:45Z","timestamp":1750235745000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2390176.2390189"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,12]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2012,12]]}},"alternative-id":["10.1145\/2390176.2390189"],"URL":"https:\/\/doi.org\/10.1145\/2390176.2390189","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2012,12]]},"assertion":[{"value":"2010-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-12-26","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}