{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,11]],"date-time":"2026-11-11T07:11:21Z","timestamp":1794381081523,"version":"4.9.0"},"publisher-location":"Berlin, Heidelberg","reference-count":16,"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_66","type":"book-chapter","created":{"date-parts":[[2010,9,15]],"date-time":"2010-09-15T18:53:21Z","timestamp":1284576801000},"page":"782-792","source":"Crossref","is-referenced-by-count":15,"title":["Closest Pair Problems in Very High Dimensions"],"prefix":"10.1007","author":[{"given":"Piotr","family":"Indyk","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Moshe","family":"Lewenstein","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ohad","family":"Lipsky","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ely","family":"Porat","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"issue":"6","key":"66_CR1","doi-asserted-by":"publisher","first-page":"1039","DOI":"10.1137\/0216067","volume":"16","author":"K. Abrahamson","year":"1987","unstructured":"Abrahamson, K.: Generalized string matching. SIAM J. Computing\u00a016(6), 1039\u20131051 (1987)","journal-title":"SIAM J. Computing"},{"issue":"2","key":"66_CR2","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1006\/jagm.1996.0850","volume":"24","author":"A. Amir","year":"1997","unstructured":"Amir, A., Apostolico, A., Lewenstein, M.: Inverse Pattern Matching. J. of Algorithms\u00a024(2), 325\u2013339 (1997)","journal-title":"J. of Algorithms"},{"issue":"1","key":"66_CR3","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1006\/inco.1995.1047","volume":"118","author":"A. Amir","year":"1995","unstructured":"Amir, A., Farach, M.: Efficient 2-dimensional approximate matching of half-rectangular figures. Information and Computation\u00a0118(1), 1\u201311 (1995)","journal-title":"Information and Computation"},{"key":"66_CR4","unstructured":"Amir, A., Porat, E., Lewenstein, M.: Faster algorithms for string matching with k mismatches. J. of Algorithms, special SODA 2000 issue (2000) (to appear)"},{"key":"66_CR5","doi-asserted-by":"crossref","unstructured":"Borodin, A., Ostrovsky, R., Rabani, Y.: Subquadratic approximation algorithms for clustering problems in high dimensional spaces. In: Proceedings of the Symposium on Theory of Computing (1999)","DOI":"10.1145\/301250.301367"},{"key":"66_CR6","doi-asserted-by":"crossref","unstructured":"Datar, M., Immorlica, N., Indyk, P., Mirrokni, V.: Locality-sensitive hashing scheme based on p-stable distributions. In: Proc. of Symposium of Computational Geometry, SOCG (2004) (to appear)","DOI":"10.1145\/997817.997857"},{"issue":"2","key":"66_CR7","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1145\/174652.174653","volume":"41","author":"M. Dubiner","year":"1994","unstructured":"Dubiner, M., Galil, Z., Magen, E.: Faster tree pattern matching. J. of the ACM\u00a041(2), 205\u2013213 (1994)","journal-title":"J. of the ACM"},{"key":"66_CR8","doi-asserted-by":"crossref","unstructured":"Indyk, P., Motwani, R.: Approximate nearest neighbor: towards removing the curse of dimensionality. In: Proceedings of the Symposium on Theory of Computing (1998)","DOI":"10.1145\/276698.276876"},{"key":"66_CR9","unstructured":"Indyk, P.: High-dimensional computational geometry. Ph.D. Thesis, Department of Computer Science, Stanford University (2001)"},{"key":"66_CR10","doi-asserted-by":"crossref","unstructured":"Kosaraju, R.: Efficient tree pattern matching. In: Proc. of Symosium on Foundation of Computer Science (1990)","DOI":"10.1109\/SFCS.1989.63475"},{"key":"66_CR11","doi-asserted-by":"crossref","unstructured":"Kleinberg, J.: Two algorithms for nearest-neighbor search in high dimensions. In: Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing (1997)","DOI":"10.1145\/258533.258653"},{"key":"66_CR12","unstructured":"Lipsky, O., Porat, E.: Approximated Pattern Matching with the L1 L2 and L\u2009\u221e\u2009 Metrics. Submitted to SODA 2004 (2004) (manuscript)"},{"key":"66_CR13","series-title":"Lecture Notes in Computer Science","volume-title":"Combinatorial Pattern Matching","author":"S. Muthukrishnan","year":"1995","unstructured":"Muthukrishnan, S.: New results and open problems related to non-standard stringology. In: Galil, Z., Ukkonen, E. (eds.) CPM 1995. LNCS, vol.\u00a0937, Springer, Heidelberg (1995)"},{"key":"66_CR14","doi-asserted-by":"crossref","unstructured":"Muthukrishnan, S., Palem, K.: Non-standard stringology: algorithms and complexity. In: Proc. of the ACM Symposium on Theory of Computing, pp. 770\u2013779 (1994)","DOI":"10.1145\/195058.195457"},{"key":"66_CR15","first-page":"21","volume-title":"Algorithms and Complexity","author":"M.O. Rabin","year":"1976","unstructured":"Rabin, M.O.: Probabilistic algorithms. In: Traub, J.F. (ed.) Algorithms and Complexity, pp. 21\u201339. Academic Press, London (1976)"},{"key":"66_CR16","doi-asserted-by":"crossref","unstructured":"Shamos, I., Bentley, J.: Divide-and-conquer in multidimensional space. In: Proceedings of the Symposium on Theory of Computing, pp. 220\u2013230 (1976)","DOI":"10.1145\/800113.803652"}],"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_66.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,18]],"date-time":"2020-11-18T23:24:04Z","timestamp":1605741844000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-27836-8_66"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004]]},"ISBN":["9783540228493","9783540278368"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-27836-8_66","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]]}}}