{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:53:47Z","timestamp":1750308827099,"version":"3.41.0"},"reference-count":13,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2010,7,1]],"date-time":"2010-07-01T00:00:00Z","timestamp":1277942400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGSPATIAL Special"],"published-print":{"date-parts":[[2010,7]]},"abstract":"<jats:p>\n            <jats:bold>Why?<\/jats:bold>\n            The metric search paradigm has been to this day successfully applied to several real-world problems, ranging from multimedia to data mining, from decision support to pattern recognition, to statistical and medical applications. Indeed, its simplicity makes it a perfect candidate for solving a variety of similarity problems arising in applications [4, 11]. The casual reader may wonder what prevents the metric space paradigm to become ubiquitously applicable to the ever-increasing range of applications that can benefit from it. The answer to this question is so dreadful that researchers have given it the hideous name of \"\n            <jats:italic>curse of dimensionality\"<\/jats:italic>\n            (an entry in this issue of the bulletin is devoted to this concept). In its essence, the curse of dimensionality says that, whenever the (intrinsic) dimensionality\n            <jats:italic>D<\/jats:italic>\n            of the metric space is high, an efficient solution to NN (nearest neighbor) queries. is impossible, and only a sequential scan of the whole dataset could guarantee that the correct result is found. This behavior is basically due to the fact that the variance of the distances to the query object\n            <jats:italic>q<\/jats:italic>\n            vanishes with increasing values of\n            <jats:italic>D<\/jats:italic>\n            , so that all data objects have almost the same distance to\n            <jats:italic>q<\/jats:italic>\n            . In such scenarios, one may however argue that NN queries lose of significance, since any data object would have a distance to the query object comparable to the minimal one [2]. On the other hand, in several real-world cases searching for the exact NN is still difficult, yet the distribution of distances exhibits a sufficiently high variance to make the problem worth solving. In such cases, it is also observed that locating the NN of a query point is, in itself, a relatively easy task, whose complexity indeed\n            <jats:italic>decreases<\/jats:italic>\n            with space dimensionality. As a matter of fact, the hard problem in high-\n            <jats:italic>D<\/jats:italic>\n            exact NN search is to determine how to stop, i.e., how to guarantee that the current result is the correct one. From this it follows that\n            <jats:italic>most of the time spent in an (exact) NN search is wasted time, during which little (or no) improvement is obtained<\/jats:italic>\n            [5].\n          <\/jats:p>","DOI":"10.1145\/1862413.1862418","type":"journal-article","created":{"date-parts":[[2010,9,22]],"date-time":"2010-09-22T11:55:58Z","timestamp":1285156558000},"page":"16-19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Approximate and probabilistic methods"],"prefix":"10.1145","volume":"2","author":[{"given":"Paolo","family":"Ciaccia","sequence":"first","affiliation":[{"name":"Universit\u00e0 di Bologna, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Marco","family":"Patella","sequence":"additional","affiliation":[{"name":"Universit\u00e0 di Bologna, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2010,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/312129.312236"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/645503.656271"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2007.70815"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the 1st International Workshop on Similarity Search and Applications (SISAP 2008","author":"Ch\u00e1vez E.","year":"2008","unstructured":"}} E. Ch\u00e1vez and G. Navarro , editors . Proceedings of the 1st International Workshop on Similarity Search and Applications (SISAP 2008 ), Canc\u00fan, Mexico , Apr. 2008 . }}E. Ch\u00e1vez and G. Navarro, editors. Proceedings of the 1st International Workshop on Similarity Search and Applications (SISAP 2008), Canc\u00fan, Mexico, Apr. 2008."},{"key":"e_1_2_1_5_1","first-page":"244","volume-title":"ICDE 2000","author":"Ciaccia P.","year":"2000","unstructured":"}} P. Ciaccia and M. Patella . PAC NN queries: Approximate and controlled search in high-dimensional and metric spaces . In ICDE 2000 , pp. 244 -- 255 , San Diego, CA , Mar. 2000 . }}P. Ciaccia and M. Patella. PAC NN queries: Approximate and controlled search in high-dimensional and metric spaces. In ICDE 2000, pp. 244--255, San Diego, CA, Mar. 2000."},{"key":"e_1_2_1_6_1","first-page":"518","volume-title":"VLDB'99","author":"Gionis A.","year":"1999","unstructured":"}} A. Gionis , P. Indyk , and R. Motwani . Similarity search in high dimensions via hashing . In VLDB'99 , pp. 518 -- 529 , Edinburgh, Scotland, UK , Sept. 1999 . }}A. Gionis, P. Indyk, and R. Motwani. Similarity search in high dimensions via hashing. In VLDB'99, pp. 518--529, Edinburgh, Scotland, UK, Sept. 1999."},{"key":"e_1_2_1_7_1","first-page":"506","volume-title":"VLDB 2000","author":"Hinneburg A.","year":"2000","unstructured":"}} A. Hinneburg , C. C. Aggarwal , and D. A. Keim . What is the nearest neighbor in high dimensional spaces ? In VLDB 2000 , pp. 506 -- 515 , Cairo, Egypt , Sept. 2000 . }}A. Hinneburg, C. C. Aggarwal, and D. A. Keim. What is the nearest neighbor in high dimensional spaces? In VLDB 2000, pp. 506--515, Cairo, Egypt, Sept. 2000."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/SISAP.2008.18"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2008.09.014"},{"key":"e_1_2_1_10_1","volume-title":"Morgan Kaufmann","author":"Samet H.","year":"2006","unstructured":"}} H. Samet . Foundations of Multidimensional and Metric Data Structures . Morgan Kaufmann , 2006 . }}H. Samet. Foundations of Multidimensional and Metric Data Structures. Morgan Kaufmann, 2006."},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 2nd International Workshop on Similarity Search and Applications (SISAP 2009","author":"Skopal T.","year":"2009","unstructured":"}} T. Skopal and P. Zezula , editors . Proceedings of the 2nd International Workshop on Similarity Search and Applications (SISAP 2009 ), Prague, Czech Republic , Sept. 2009 . }}T. Skopal and P. Zezula, editors. Proceedings of the 2nd International Workshop on Similarity Search and Applications (SISAP 2009), Prague, Czech Republic, Sept. 2009."},{"key":"e_1_2_1_12_1","first-page":"194","volume-title":"VLDB'98","author":"Weber R.","year":"1998","unstructured":"}} R. Weber , H. Schek , and S. Blott . A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces . In VLDB'98 , pp. 194 -- 205 , New York City, NY , Aug. 1998 . }}R. Weber, H. Schek, and S. Blott. A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces. In VLDB'98, pp. 194--205, New York City, NY, Aug. 1998."},{"key":"e_1_2_1_13_1","series-title":"Advances in Database Systems","doi-asserted-by":"crossref","DOI":"10.1007\/0-387-29151-2","volume-title":"Similarity Search - The Metric Space Approach","author":"Zezula P.","year":"2006","unstructured":"}} P. Zezula , G. Amato , V. Dohnal , and M. Batko . Similarity Search - The Metric Space Approach , volume 32 of Advances in Database Systems . Springer , 2006 . }}P. Zezula, G. Amato, V. Dohnal, and M. Batko. Similarity Search - The Metric Space Approach, volume 32 of Advances in Database Systems. Springer, 2006."}],"container-title":["SIGSPATIAL Special"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1862413.1862418","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1862413.1862418","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:26:55Z","timestamp":1750278415000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1862413.1862418"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,7]]},"references-count":13,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2010,7]]}},"alternative-id":["10.1145\/1862413.1862418"],"URL":"https:\/\/doi.org\/10.1145\/1862413.1862418","relation":{},"ISSN":["1946-7729"],"issn-type":[{"type":"electronic","value":"1946-7729"}],"subject":[],"published":{"date-parts":[[2010,7]]},"assertion":[{"value":"2010-07-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}