{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,3]],"date-time":"2026-10-03T06:01:02Z","timestamp":1791007262365,"version":"4.1.0"},"reference-count":16,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2006,9]]},"abstract":"<jats:p>\n            In this article, we consider whether traditional index structures are effective in processing unstable nearest neighbors workloads. It is known that under broad conditions, nearest neighbors workloads become\n            <jats:italic>unstable<\/jats:italic>\n            ---distances between data points become indistinguishable from each other. We complement this earlier result by showing that if the workload for an application is unstable, you are not likely to be able to index it efficiently using (almost all known) multidimensional index structures. For a broad class of data distributions, we prove that these index structures will do no better than a linear scan of the data as dimensionality increases.Our result has implications for how experiments should be designed on index structures such as R-Trees, X-Trees, and SR-Trees: simply put, experiments trying to establish that these index structures scale with dimensionality should be designed to establish\n            <jats:italic>crossover points<\/jats:italic>\n            , rather than to show that the methods scale to an arbitrary number of dimensions. In other words, experiments should seek to establish the dimensionality of the dataset at which the proposed index structure deteriorates to linear scan, for each data distribution of interest; that linear scan will eventually dominate is a given.An important problem is to analytically characterize the\n            <jats:italic>rate<\/jats:italic>\n            at which index structures degrade with increasing dimensionality, because the dimensionality of a real data set may well be in the range that a particular method can handle. The results in this article can be regarded as a step toward solving this problem. Although we do not characterize the rate at which a structure degrades, our techniques allow us to reason directly about a broad class of index structures rather than the geometry of the nearest neighbors problem, in contrast to earlier work.\n          <\/jats:p>","DOI":"10.1145\/1166074.1166077","type":"journal-article","created":{"date-parts":[[2006,10,18]],"date-time":"2006-10-18T18:11:32Z","timestamp":1161195092000},"page":"814-838","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":37,"title":["Theory of nearest neighbors indexability"],"prefix":"10.1145","volume":"31","author":[{"given":"Uri","family":"Shaft","sequence":"first","affiliation":[{"name":"Oracle USA, Redwood Shores, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Raghu","family":"Ramakrishnan","sequence":"additional","affiliation":[{"name":"University of Wisconsin-Madison, Madison, WI"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2006,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/93597.98741"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of VLDB. 28--39","author":"Berchtold S.","unstructured":"Berchtold , S. , Keim , D. A. , and Kriegel , H . 1996. The x-tree: An index structure for high-dimensional data . In Proceedings of VLDB. 28--39 .]] Berchtold, S., Keim, D. A., and Kriegel, H. 1996. The x-tree: An index structure for high-dimensional data. In Proceedings of VLDB. 28--39.]]"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of ICDT.]]","author":"Beyer K.","unstructured":"Beyer , K. , Goldstein , J. , Ramakrishnan , R. , and Shaft , U . 1999. When is nearest neighbors meaningful? In Proceedings of ICDT.]] Beyer, K., Goldstein, J., Ramakrishnan, R., and Shaft, U. 1999. When is nearest neighbors meaningful? In Proceedings of ICDT.]]"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of VLDB. 518--529","author":"Gionis A.","unstructured":"Gionis , A. , Indyk , P. , and Motwani , R . 1999. Similarity search in high dimensions via hashing . In Proceedings of VLDB. 518--529 .]] Gionis, A., Indyk, P., and Motwani, R. 1999. Similarity search in high dimensions via hashing. In Proceedings of VLDB. 518--529.]]"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of VLDB. 429--440","author":"Goldstein J.","unstructured":"Goldstein , J. and Ramakrishnan , R . 2000. Contrast plots and P-Sphere trees: Space vs. time in nearest neighbour searches . In Proceedings of VLDB. 429--440 .]] Goldstein, J. and Ramakrishnan, R. 2000. Contrast plots and P-Sphere trees: Space vs. time in nearest neighbour searches. In Proceedings of VLDB. 429--440.]]"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/602259.602266"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/263661.263688"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/253260.253347"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/615204.615210"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(99)00156-8"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/582318.582321"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of VLDB. 507--518","author":"Sellis T. K.","unstructured":"Sellis , T. K. , Roussopoulos , N. , and Faloutsos , C. H . 1987. The R&plus;-Tree: A dynamic index for multi-dimensional objects . In Proceedings of VLDB. 507--518 .]] Sellis, T. K., Roussopoulos, N., and Faloutsos, C. H. 1987. The R&plus;-Tree: A dynamic index for multi-dimensional objects. In Proceedings of VLDB. 507--518.]]"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30570-5_11"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of SPIE 3656: Storage and Retrieval for Image and Video Databases VII. 511--522","author":"Smith J. R.","year":"1998","unstructured":"Smith , J. R. 1998 . Query vector projection access method . In Proceedings of SPIE 3656: Storage and Retrieval for Image and Video Databases VII. 511--522 .]] Smith, J. R. 1998. Query vector projection access method. In Proceedings of SPIE 3656: Storage and Retrieval for Image and Video Databases VII. 511--522.]]"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of VLDB. 194--205","author":"Weber R.","unstructured":"Weber , R. , Schek , H. , and Blott , S. A . 1998. Quantitative analysis and performance study for similarity-search methods in high-dimensional spaces . In Proceedings of VLDB. 194--205 .]] Weber, R., Schek, H., and Blott, S. A. 1998. Quantitative analysis and performance study for similarity-search methods in high-dimensional spaces. In Proceedings of VLDB. 194--205.]]"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of ICDE. 516--523","author":"White D. A.","unstructured":"White , D. A. and Jain , R. C . 1996. Similarity indexing with the SS-tree . In Proceedings of ICDE. 516--523 .]] White, D. A. and Jain, R. C. 1996. Similarity indexing with the SS-tree. In Proceedings of ICDE. 516--523.]]"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1166074.1166077","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T21:20:09Z","timestamp":1672262409000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1166074.1166077"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,9]]},"references-count":16,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2006,9]]}},"alternative-id":["10.1145\/1166074.1166077"],"URL":"https:\/\/doi.org\/10.1145\/1166074.1166077","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,9]]},"assertion":[{"value":"2006-09-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}