{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,3]],"date-time":"2025-07-03T04:16:39Z","timestamp":1751516199375,"version":"3.41.0"},"publisher-location":"Cham","reference-count":33,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319774039"},{"type":"electronic","value":"9783319774046"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-77404-6_10","type":"book-chapter","created":{"date-parts":[[2018,3,12]],"date-time":"2018-03-12T10:03:11Z","timestamp":1520848991000},"page":"120-133","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Approximate Nearest Neighbor Search for $$\\ell _p$$-Spaces $$(2<p<\\infty )$$ via Embeddings"],"prefix":"10.1007","author":[{"given":"Yair","family":"Bartal","sequence":"first","affiliation":[]},{"given":"Lee-Ad","family":"Gottlieb","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,3,13]]},"reference":[{"key":"10_CR1","doi-asserted-by":"crossref","unstructured":"Ailon, N., Chazelle, B.: Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform. In: STOC 2006, pp. 557\u2013563 (2006)","DOI":"10.1145\/1132516.1132597"},{"key":"10_CR2","doi-asserted-by":"crossref","unstructured":"Andoni, A., Croitoru, D., Patrascu, M.: Hardness of nearest neighbor under L-infinity. In: Foundations of Computer Science, pp. 424\u2013433 (2008)","DOI":"10.1109\/FOCS.2008.89"},{"key":"10_CR3","unstructured":"Andoni, A.: Nearest neighbor search: the old, the new, and the impossible. Ph.D. thesis, MIT (2009)"},{"key":"10_CR4","doi-asserted-by":"crossref","unstructured":"Arya, S., Malamatos, T.: Linear-size approximate Voronoi diagrams. In: SODA 2002, pp. 147\u2013155 (2002)","DOI":"10.1145\/509907.510011"},{"issue":"4","key":"10_CR5","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1016\/S0195-6698(13)80131-X","volume":"11","author":"K Ball","year":"1990","unstructured":"Ball, K.: Isometric embedding in $$l_p$$-spaces. Eur. J. Comb. 11(4), 305\u2013311 (1990)","journal-title":"Eur. J. Comb."},{"key":"10_CR6","doi-asserted-by":"crossref","unstructured":"Batu, T., Ergun, F., Sahinalp, C.: Oblivious string embeddings and edit distance approximations. In: SODA 2006, pp. 792\u2013801 (2006)","DOI":"10.1145\/1109557.1109644"},{"key":"10_CR7","doi-asserted-by":"publisher","DOI":"10.1515\/9781400874668","volume-title":"Adaptive Control Processes: A Guided Tour","author":"RE Bellman","year":"1961","unstructured":"Bellman, R.E.: Adaptive Control Processes: A Guided Tour. Princeton University Press, Princeton (1961)"},{"issue":"2","key":"10_CR8","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1016\/0020-0190(93)90222-U","volume":"45","author":"M Bern","year":"1993","unstructured":"Bern, M.: Approximate closest-point queries in high dimensions. Inf. Process. Lett. 45(2), 95\u201399 (1993)","journal-title":"Inf. Process. Lett."},{"key":"10_CR9","doi-asserted-by":"crossref","unstructured":"Beygelzimer, A., Kakade, S., Langford, J.: Cover trees for nearest neighbor. In: ICML 2006, pp. 97\u2013104 (2006)","DOI":"10.1145\/1143844.1143857"},{"key":"10_CR10","volume-title":"Geometric Nonlinear Functional Analysis","author":"Y Binyamini","year":"2000","unstructured":"Binyamini, Y., Lindenstrauss, J.: Geometric Nonlinear Functional Analysis. Colloquium Publications (American Mathematical Society), Providence (2000)"},{"issue":"3","key":"10_CR11","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1007\/PL00009390","volume":"20","author":"TM Chan","year":"1998","unstructured":"Chan, T.M.: Approximate nearest neighbor queries revisited. Discret. Comput. Geom. 20(3), 359\u2013373 (1998)","journal-title":"Discret. Comput. Geom."},{"issue":"4","key":"10_CR12","doi-asserted-by":"publisher","first-page":"830","DOI":"10.1137\/0217052","volume":"17","author":"KL Clarkson","year":"1988","unstructured":"Clarkson, K.L.: A randomized algorithm for closest-point queries. SIAM J. Comput. 17(4), 830\u2013847 (1988)","journal-title":"SIAM J. Comput."},{"key":"10_CR13","doi-asserted-by":"crossref","unstructured":"Cole, R., Gottlieb, L.: Searching dynamic point sets in spaces with bounded doubling dimension. In: STOC 2006, pp. 574\u2013583 (2006)","DOI":"10.1145\/1132516.1132599"},{"issue":"3","key":"10_CR14","doi-asserted-by":"publisher","first-page":"1061","DOI":"10.1016\/j.patcog.2011.08.012","volume":"45","author":"RC de Amorim","year":"2012","unstructured":"de Amorim, R.C., Mirkin, B.: Minkowski metric feature weighting and anomalous cluster initializing in k-means clustering. Pattern Recogn. 45(3), 1061\u20131075 (2012)","journal-title":"Pattern Recogn."},{"key":"10_CR15","first-page":"439","volume-title":"Classification and Related Metods of Data Analysis","author":"B Fichet","year":"1988","unstructured":"Fichet, B.: $$l_p$$-spaces in data analysis. In: Bock, H.H. (ed.) Classification and Related Metods of Data Analysis, pp. 439\u2013444. North-Holland, Amsterdam (1988)"},{"key":"10_CR16","doi-asserted-by":"crossref","unstructured":"Finlayson, G.D., Rey, P.A.T., Trezzi, E.: General $$l_p$$ constrained approach for colour constancy. In: ICCV Workshops 2011, pp. 790\u2013797 (2011)","DOI":"10.1109\/ICCVW.2011.6130333"},{"key":"10_CR17","doi-asserted-by":"crossref","unstructured":"Finlayson, G.D., Trezzi, E.: Shades of gray and colour constancy. In: CIC 2004, pp. 37\u201341 (2004)","DOI":"10.2352\/CIC.2004.12.1.art00008"},{"issue":"1","key":"10_CR18","doi-asserted-by":"publisher","first-page":"321","DOI":"10.4086\/toc.2012.v008a014","volume":"8","author":"S Har-Peled","year":"2012","unstructured":"Har-Peled, S., Indyk, P., Motwani, R.: Approximate nearest neighbors: towards removing the curse of dimensionality. Theory Comput. 8(1), 321\u2013350 (2012)","journal-title":"Theory Comput."},{"issue":"5","key":"10_CR19","doi-asserted-by":"publisher","first-page":"1148","DOI":"10.1137\/S0097539704446281","volume":"35","author":"S Har-Peled","year":"2006","unstructured":"Har-Peled, S., Mendel, M.: Fast construction of nets in low-dimensional metrics and their applications. SIAM J. Comput. 35(5), 1148\u20131184 (2006)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"10_CR20","doi-asserted-by":"publisher","first-page":"944","DOI":"10.1137\/140959067","volume":"44","author":"S Har-Peled","year":"2015","unstructured":"Har-Peled, S., Kumar, N.: Approximating minimization diagrams and generalized proximity search. SIAM J. Comput. 44(4), 944\u2013974 (2015)","journal-title":"SIAM J. Comput."},{"key":"10_CR21","doi-asserted-by":"crossref","unstructured":"Indyk, P.: On approximate nearest neighbors in non-Euclidean spaces. In: FOCS, pp. 148\u2013155 (1998)","DOI":"10.1145\/276698.276876"},{"key":"10_CR22","doi-asserted-by":"crossref","unstructured":"Indyk, P., Motwani, R.: Approximate nearest neighbors: towards removing the curse of dimensionality. In: STOC 1998, pp. 604\u2013613 (1998)","DOI":"10.1145\/276698.276876"},{"issue":"3","key":"10_CR23","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1145\/1273340.1273347","volume":"3","author":"P Indyk","year":"2007","unstructured":"Indyk, P., Naor, A.: Nearest-neighbor-preserving embeddings. ACM Trans. Algorithms 3(3), 31 (2007)","journal-title":"ACM Trans. Algorithms"},{"key":"10_CR24","doi-asserted-by":"crossref","unstructured":"Johnson, W.B., Lindenstrauss, J.: Extensions of Lipschitz mappings into a Hilbert space. In: Conference in Modern Analysis and Probability, New Haven, Connecticut, 1982, pp. 189\u2013206. American Mathematical Society, Providence (1984)","DOI":"10.1090\/conm\/026\/737400"},{"issue":"1\u20132","key":"10_CR25","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/BF02392350","volume":"149","author":"WB Johnson","year":"1982","unstructured":"Johnson, W.B., Schechtman, G.: Embedding $$l_p^m$$ into $$l_1^n$$. Acta Math. 149(1\u20132), 71\u201385 (1982)","journal-title":"Acta Math."},{"key":"10_CR26","unstructured":"Krauthgamer, R., Lee, J.R.: Navigating nets: simple algorithms for proximity search. In: SODA 2004, pp. 791\u2013801 (2004)"},{"key":"10_CR27","doi-asserted-by":"crossref","unstructured":"Kushilevitz, E., Ostrovsky, R., Rabani, Y.: Efficient search for approximate nearest neighbor in high dimensional spaces. In: STOC 1998, pp. 614\u2013623 (1998)","DOI":"10.1145\/276698.276877"},{"issue":"1","key":"10_CR28","first-page":"1","volume":"2","author":"A Naor","year":"2014","unstructured":"Naor, A.: Comparison of metric spectral gaps. Anal. Geome. Metr. Spaces 2(1), 1\u201352 (2014)","journal-title":"Anal. Geome. Metr. Spaces"},{"key":"10_CR29","unstructured":"Naor, A., Rabani, Y.: On approximate nearest neighbor search in $$\\ell _p$$, $$p >2$$ (2006, manuscript)"},{"key":"10_CR30","doi-asserted-by":"crossref","unstructured":"Neylon, T.: A locality-sensitive hash for real vectors. In: SODA 2010, pp. 1179\u20131189 (2010)","DOI":"10.1137\/1.9781611973075.94"},{"key":"10_CR31","doi-asserted-by":"crossref","unstructured":"Ostrovsky, R., Rabani, Y.: Polynomial time approximation schemes for geometric k-clustering. In: FOCS 2000, pp. 349\u2013358 (2000)","DOI":"10.1109\/SFCS.2000.892123"},{"issue":"2","key":"10_CR32","doi-asserted-by":"publisher","first-page":"139","DOI":"10.1145\/506147.506149","volume":"49","author":"R Ostrovsky","year":"2002","unstructured":"Ostrovsky, R., Rabani, Y.: Polynomial-time approximation schemes for geometric min-sum median clustering. J. ACM 49(2), 139\u2013156 (2002)","journal-title":"J. ACM"},{"key":"10_CR33","doi-asserted-by":"crossref","unstructured":"Yu, D., Yu, X., Wu, A.: Making the nearest neighbor meaningful for time series classification. In: CISP 2011, pp. 2481\u20132485 (2011)","DOI":"10.1109\/CISP.2011.6100672"}],"container-title":["Lecture Notes in Computer Science","LATIN 2018: Theoretical Informatics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-77404-6_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,2]],"date-time":"2025-07-02T18:29:11Z","timestamp":1751480951000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-77404-6_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319774039","9783319774046"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-77404-6_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"13 March 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"LATIN","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Latin American Symposium on Theoretical Informatics","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Buenos Aires","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Argentina","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16 April 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"19 April 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"latin2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/latin2018.dc.uba.ar\/#","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}