{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,16]],"date-time":"2026-06-16T11:50:20Z","timestamp":1781610620312,"version":"3.54.5"},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540265467","type":"print"},{"value":"9783540316824","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11505877_3","type":"book-chapter","created":{"date-parts":[[2010,9,26]],"date-time":"2010-09-26T13:40:25Z","timestamp":1285508425000},"page":"22-35","source":"Crossref","is-referenced-by-count":3,"title":["Locally Consistent Parsing and Applications to Approximate String Comparisons"],"prefix":"10.1007","author":[{"given":"Tu\u011fkan","family":"Batu","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"S. Cenk","family":"Sahinalp","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"3_CR1","unstructured":"Alstrup, S., St\u00f8lting Brodal, G., Rauhe, T.: Pattern matching in dynamic texts. In: SODA 2000: Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms, pp. 819\u2013828 (2000)"},{"key":"3_CR2","unstructured":"Bar-Yossef, Z., Jayram, T.S., Krauthgamer, R., Kumar, R.: Approximating edit distance efficiently. In: IEEE Symposium on Foundations of Computer Science, FOCS (2004)"},{"key":"3_CR3","doi-asserted-by":"crossref","unstructured":"Batu, T., Ergun, F., Cenk Sahinalp, S.: Oblivious string embeddings and edit distance approximations. Technical Report TR2005-11, School of Computing Science, Simon Fraser University (2005)","DOI":"10.1145\/1109557.1109644"},{"key":"3_CR4","unstructured":"Cole, R., Hariharan, R.: Approximate string matching: A simpler faster algorithm. In: SODA, pp. 463\u2013472 (1998)"},{"key":"3_CR5","doi-asserted-by":"crossref","unstructured":"Cole, R., Vishkin, U.: Deterministic coin tossing and accelerating cascades: Micro and macro techniques for designing parallel algorithms. In: ACM Symposium on Theory of Computing, STOC (1986)","DOI":"10.1145\/12130.12151"},{"key":"3_CR6","unstructured":"Cormode, G., Muthukrishnan, S.: The string edit distance matching problem with moves. In: SODA, pp. 667\u2013676 (2002)"},{"key":"3_CR7","unstructured":"Cormode, G., Muthukrishnan, S.: Substring compression problems. SODA (2005)"},{"issue":"2","key":"3_CR8","doi-asserted-by":"publisher","first-page":"338","DOI":"10.1137\/0213024","volume":"13","author":"D. Harel","year":"1984","unstructured":"Harel, D., Tarjan, R.E.: Fast algorithms for finding nearest common ancestors. SIAM Journal on Computing\u00a013(2), 338\u2013355 (1984)","journal-title":"SIAM Journal on Computing"},{"key":"3_CR9","doi-asserted-by":"crossref","unstructured":"Indyk, P., Motwani, R.: Approximate nearest neighbors: Towards removing the curse of dimensionality. In: STOC, pp. 604\u2013613 (1998)","DOI":"10.1145\/276698.276876"},{"key":"3_CR10","doi-asserted-by":"crossref","unstructured":"Kushilevitz, E., Ostrovsky, R., Rabani, Y.: Efficient search for approximate nearest neighbor in high dimensional spaces. In: STOC, pp. 614\u2013623 (1998)","DOI":"10.1145\/276698.276877"},{"issue":"1","key":"3_CR11","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1016\/0022-0000(80)90002-1","volume":"20","author":"W.J. Masek","year":"1980","unstructured":"Masek, W.J., Paterson, M.S.: A faster algorithm computing string edit distances. Journal of Computer and System Sciences\u00a020(1), 18\u201331 (1980)","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"3_CR12","doi-asserted-by":"publisher","first-page":"262","DOI":"10.1145\/321941.321946","volume":"23","author":"E.M. McCreight","year":"1976","unstructured":"McCreight, E.M.: A space-economical suffix tree construction algorithm. J. ACM\u00a023(2), 262\u2013272 (1976)","journal-title":"J. ACM"},{"key":"3_CR13","unstructured":"Mehlhorn, K., Sundar, R., Uhrig, C.: Maintaining dynamic sequences under equality-tests in polylogarithmic time. In: SODA, pp. 213\u2013222 (1994)"},{"key":"3_CR14","doi-asserted-by":"crossref","unstructured":"Muthukrishnan, S., Cenk Sahinalp, S.: Approximate nearest neighbors and sequence comparison with block operations. In: STOC, pp. 416\u2013424 (2000)","DOI":"10.1145\/335305.335353"},{"key":"3_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1007\/3-540-57811-0_3","volume-title":"Algorithms and Complexity","author":"S. Cenk Sahinalp","year":"1994","unstructured":"Cenk Sahinalp, S., Vishkin, U.: On a parallel-algorithms method for string matching problems. In: Bonuccelli, M.A., Crescenzi, P., Petreschi, R. (eds.) CIAC 1994. LNCS, vol.\u00a0778, pp. 22\u201332. Springer, Heidelberg (1994)"},{"key":"3_CR16","doi-asserted-by":"crossref","unstructured":"Cenk Sahinalp, S., Vishkin, U.: Symmetry breaking for suffix tree construction. In: STOC, pp. 300\u2013309 (1994)","DOI":"10.1145\/195058.195164"},{"key":"3_CR17","unstructured":"Cenk Sahinalp, S., Vishkin, U.: Data compression using locally consistent parsing. UMIACS Technical Report (1995)"},{"key":"3_CR18","doi-asserted-by":"crossref","unstructured":"Cenk Sahinalp, S., Vishkin, U.: Efficient approximate and dynamic matching of patterns using a labeling paradigm. In: IEEE Symposium on Foundations of Computer Science, FOCS (1996)","DOI":"10.1109\/SFCS.1996.548491"},{"issue":"6","key":"3_CR19","doi-asserted-by":"publisher","first-page":"1253","DOI":"10.1137\/0217079","volume":"17","author":"B. Schieber","year":"1988","unstructured":"Schieber, B., Vishkin, U.: On finding lowest common ancestors: Simplification and parallelization. SIAM Journal on Computing\u00a017(6), 1253\u20131262 (1988)","journal-title":"SIAM Journal on Computing"}],"container-title":["Lecture Notes in Computer Science","Developments in Language Theory"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11505877_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,4]],"date-time":"2019-06-04T22:50:26Z","timestamp":1559688626000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11505877_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540265467","9783540316824"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/11505877_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005]]}}}