{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,11]],"date-time":"2026-11-11T07:11:12Z","timestamp":1794381072579,"version":"4.9.0"},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540228493","type":"print"},{"value":"9783540278368","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2004]]},"DOI":"10.1007\/978-3-540-27836-8_90","type":"book-chapter","created":{"date-parts":[[2010,9,15]],"date-time":"2010-09-15T18:53:21Z","timestamp":1284576801000},"page":"1080-1098","source":"Crossref","is-referenced-by-count":5,"title":["Hardness of String Similarity Search and Other Indexing Problems"],"prefix":"10.1007","author":[{"given":"S. Cenk","family":"Sahinalp","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andrey","family":"Utis","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"90_CR1","doi-asserted-by":"crossref","unstructured":"Barkol, O., Rabani, Y.: Tighter lower bounds for nearest neighbor search and related problems in the cell probe model. In: Proc. of STOC (2000)","DOI":"10.1145\/335305.335350"},{"key":"90_CR2","doi-asserted-by":"crossref","unstructured":"Borodin, A., Ostrovsky, R., Rabani, Y.: Lower bounds for high-dimensional nearest neighbor search and related problems. In: Proc. of STOC (1999)","DOI":"10.1145\/301250.301330"},{"key":"90_CR3","doi-asserted-by":"publisher","first-page":"46","DOI":"10.1007\/BF02776078","volume":"52","author":"J. Bourgain","year":"1985","unstructured":"Bourgain, J.: On Lipschitz embedding of finite metric spaces in Hilbert space. Israel Journal of Mathematics\u00a052, 46\u201352 (1985)","journal-title":"Israel Journal of Mathematics"},{"key":"90_CR4","doi-asserted-by":"crossref","unstructured":"Chakrabarti, A., Chazelle, B., Gum, B., Lvov, A.: A Lower Bound on the Complexity of Approximate Nearest-Neighbor Searching on the Hamming Cube. In: Proc. ACM STOC (1999)","DOI":"10.1145\/301250.301325"},{"key":"90_CR5","unstructured":"Chakrabarti, A., Regev, O.: An optimal randomized cell probe lower bound for approximate nearest neighbor searching. In: ECCC (2003)"},{"key":"90_CR6","unstructured":"Cormode, G., Paterson, M., Sahinalp, S.C., Vishkin, U.: Communication Complexity of Document Exchange. In: Proc. ACM-SIAM Symp. on Discrete Algorithms (2000)"},{"key":"90_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"481","DOI":"10.1007\/3-540-48224-5_40","volume-title":"Automata, Languages and Programming","author":"G. Cormode","year":"2001","unstructured":"Cormode, G., Muthukrishnan, S., Sahinalp, S.C.: Permutation Edit Distance and Matching via Embeddings. In: Orejas, F., Spirakis, P.G., van Leeuwen, J. (eds.) ICALP 2001. LNCS, vol.\u00a02076, p. 481. Springer, Heidelberg (2001)"},{"key":"90_CR8","doi-asserted-by":"crossref","unstructured":"Farach-Colton, M., Indyk, P.: Approximate nearest neighbor algorithms for Hausdorff metrics via embeddings. In: Proc. of FOCS (1999)","DOI":"10.1109\/SFFCS.1999.814589"},{"key":"90_CR9","volume-title":"Pattern Matching Algorithms","author":"D. Hirschberg","year":"1997","unstructured":"Hirschberg, D., Galil: Serial Computations of Levenshtein Distances. In: Apostolico (ed.) Pattern Matching Algorithms, Oxford Univ. Press, Oxford (1997)"},{"key":"90_CR10","doi-asserted-by":"crossref","unstructured":"Indyk, P.: Approximate nearest neighbors in l\u2009\u221e\u2009. In: Proc. of FOCS (1998)","DOI":"10.1145\/276698.276876"},{"key":"90_CR11","doi-asserted-by":"crossref","unstructured":"Indyk, P.: Approximate nearest neighbor algorithms for Frechet metric via product metrics. In: Proc. of Symp. on Computational Geometry (2002)","DOI":"10.1145\/513400.513414"},{"key":"90_CR12","unstructured":"Indyk, P.: Better Algorithms for High-dimensional Proximity Problems via Asymmetric Embeddings. In: Proc. of 14th SODA (2003)"},{"key":"90_CR13","doi-asserted-by":"crossref","unstructured":"Indyk, P., Motwani, R.: Approximate nearest neighbors: Towards removing the curse of dimensionality. In: Proc. of 30th STOC (1998)","DOI":"10.1145\/276698.276876"},{"key":"90_CR14","doi-asserted-by":"crossref","unstructured":"Jayram, T.S., Khot, S., Kumar, R., Rabani, Y.: Cell-Probe Lower Bounds for the Partial Match Problem. In: Proc. of STOC (2003)","DOI":"10.1145\/780542.780639"},{"key":"90_CR15","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1137\/0405044","volume":"5","author":"B. Kalyanasundaram","year":"1992","unstructured":"Kalyanasundaram, B., Schnitger, G.: The Probabilistic Communication Complexity of Set Intersection. SIAM Journal on Discrete Mathematics\u00a05, 545\u2013557 (1992)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"90_CR16","doi-asserted-by":"crossref","unstructured":"Kushilevitz, E., Ostrovsky, R., Rabani, Y.: Efficient search for approximate nearest neighbor in high dimensional spaces. In: Proc. of 30th STOC (1998)","DOI":"10.1145\/276698.276877"},{"key":"90_CR17","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/BF01200757","volume":"15","author":"N. Linial","year":"1995","unstructured":"Linial, N., London, E., Rabinovich, Y.: The geometry of graphs and some of its algorithmic applications. Combinatorica\u00a015, 215\u2013245 (1995)","journal-title":"Combinatorica"},{"key":"90_CR18","unstructured":"Liu, D.: A strong lower bound for approximate nearest neighbor searching in the cell probe model (2003) (manuscript)"},{"key":"90_CR19","doi-asserted-by":"crossref","unstructured":"Miltersen, P.B.: Lower bounds for union-split-find related problems on random access machines. In: Proc. of 26th STOC (1994)","DOI":"10.1145\/195058.195415"},{"issue":"1","key":"90_CR20","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1006\/jcss.1998.1577","volume":"57","author":"P.B. Miltersen","year":"1998","unstructured":"Miltersen, P.B., Nisan, N., Safra, S., Wigderson, A.: On data structures and asymmetric communication complexity. Journal of Computer and System Sciences\u00a057(1), 37\u201349 (1998)","journal-title":"Journal of Computer and System Sciences"},{"key":"90_CR21","doi-asserted-by":"crossref","unstructured":"Muthukrishnan, S., Sahinalp, C.: Approximate nearest neighbors and sequence comparison with block operations. In: Proc. of 32nd STOC (2000)","DOI":"10.1145\/335305.335353"}],"container-title":["Lecture Notes in Computer Science","Automata, Languages and Programming"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-27836-8_90.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,18]],"date-time":"2020-11-18T23:24:09Z","timestamp":1605741849000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-27836-8_90"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540228493","9783540278368"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-27836-8_90","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/b99859","asserted-by":"object"}]},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004]]}}}