{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,2]],"date-time":"2026-05-02T16:00:25Z","timestamp":1777737625490,"version":"3.51.4"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2005,6]]},"abstract":"<jats:p>\n            In this article, we present an efficient B\n            <jats:sup>+<\/jats:sup>\n            -tree based indexing method, called iDistance, for K-nearest neighbor (KNN) search in a high-dimensional metric space. iDistance partitions the data based on a space- or data-partitioning strategy, and selects a reference point for each partition. The data points in each partition are transformed into a single dimensional value based on their similarity with respect to the reference point. This allows the points to be indexed using a B\n            <jats:sup>+<\/jats:sup>\n            -tree structure and KNN search to be performed using one-dimensional range search. The choice of partition and reference points adapts the index structure to the data distribution.We conducted extensive experiments to evaluate the iDistance technique, and report results demonstrating its effectiveness. We also present a cost model for iDistance KNN search, which can be exploited in query optimization.\n          <\/jats:p>","DOI":"10.1145\/1071610.1071612","type":"journal-article","created":{"date-parts":[[2005,8,3]],"date-time":"2005-08-03T08:30:55Z","timestamp":1123057855000},"page":"364-397","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":482,"title":["iDistance"],"prefix":"10.1145","volume":"30","author":[{"given":"H. V.","family":"Jagadish","sequence":"first","affiliation":[{"name":"University of Michigan, Ann Arbor, MI"}]},{"given":"Beng Chin","family":"Ooi","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore"}]},{"given":"Kian-Lee","family":"Tan","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore"}]},{"given":"Cui","family":"Yu","sequence":"additional","affiliation":[{"name":"Monmouth University, West Long Branch, NJ"}]},{"given":"Rui","family":"Zhang","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore"}]}],"member":"320","published-online":{"date-parts":[[2005,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304188"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 573--582","author":"Arya S.","unstructured":"Arya , S. , Mount , D. , Netanyahu , N. , Silverman , R. , and Wu , A . 1994. An optimal algorithm for approximate nearest neighbor searching . In Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 573--582 .]] Arya, S., Mount, D., Netanyahu, N., Silverman, R., and Wu, A. 1994. An optimal algorithm for approximate nearest neighbor searching. In Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 573--582.]]"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/293347.293348"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the International Conference on Data Engineering. 577--588","author":"Berchtold S.","unstructured":"Berchtold , S. , B\u00f6hm , C. , Jagadish , H. , Kriegel , H. , and Sander , J . 2000. Independent quantization: An index compression technique for high-dimensional data spaces . In Proceedings of the International Conference on Data Engineering. 577--588 .]] Berchtold, S., B\u00f6hm, C., Jagadish, H., Kriegel, H., and Sander, J. 2000. Independent quantization: An index compression technique for high-dimensional data spaces. In Proceedings of the International Conference on Data Engineering. 577--588.]]"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/276304.276318"},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the International Conference on Data Engineering. 209--218","author":"Berchtold S.","unstructured":"Berchtold , S. , Ertl , B. , Keim , D. , Kriegel , H.-P. , and Seidl , T . 1998b. Fast nearest neighbor search in high-dimensional space . In Proceedings of the International Conference on Data Engineering. 209--218 .]] Berchtold, S., Ertl, B., Keim, D., Kriegel, H.-P., and Seidl, T. 1998b. Fast nearest neighbor search in high-dimensional space. In Proceedings of the International Conference on Data Engineering. 209--218.]]"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the International Conference on Very Large Data Bases. 28--37","author":"Berchtold S.","unstructured":"Berchtold , S. , Keim , D. , and Kriegel , H . 1996. The X-tree: An index structure for high-dimensional data . In Proceedings of the International Conference on Very Large Data Bases. 28--37 .]] Berchtold, S., Keim, D., and Kriegel, H. 1996. The X-tree: An index structure for high-dimensional data. In Proceedings of the International Conference on Very Large Data Bases. 28--37.]]"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the International Conference on Database Theory.]]","author":"Beyer K.","unstructured":"Beyer , K. , Goldstein , J. , Ramakrishnan , R. , and Shaft , U . 1999. When is nearest neighbors meaningful? In Proceedings of the International Conference on Database Theory.]] Beyer, K., Goldstein, J., Ramakrishnan, R., and Shaft, U. 1999. When is nearest neighbors meaningful? In Proceedings of the International Conference on Database Theory.]]"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/502807.502809"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/253260.253345"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the International Conference on Data Engineering. 322--331","author":"Chakrabarti K.","unstructured":"Chakrabarti , K. and Mehrotra , S . 1999. The hybrid tree: An index structure for high dimensional feature spaces . In Proceedings of the International Conference on Data Engineering. 322--331 .]] Chakrabarti, K. and Mehrotra, S. 1999. The hybrid tree: An index structure for high dimensional feature spaces. In Proceedings of the International Conference on Data Engineering. 322--331.]]"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the International Conference on Very Large Databases. 89--100","author":"Chakrabarti K.","unstructured":"Chakrabarti , K. and Mehrotra , S . 2000. Local dimensionality reduction: a new approach to indexing high dimensional spaces . In Proceedings of the International Conference on Very Large Databases. 89--100 .]] Chakrabarti, K. and Mehrotra, S. 2000. Local dimensionality reduction: a new approach to indexing high dimensional spaces. In Proceedings of the International Conference on Very Large Databases. 89--100.]]"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the International Conference on Very Large Data Bases. 426--435","author":"Ciaccia P.","unstructured":"Ciaccia , P. , Patella , M. , and Zezula , P . 1997. M-trees: An efficient access method for similarity search in metric space . In Proceedings of the International Conference on Very Large Data Bases. 426--435 .]] Ciaccia, P., Patella, M., and Zezula, P. 1997. M-trees: An efficient access method for similarity search in metric space. In Proceedings of the International Conference on Very Large Data Bases. 426--435.]]"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872815"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2005.46"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/223784.223812"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the International Conference on Data Engineering. 623--630","author":"Filho R. F. S.","unstructured":"Filho , R. F. S. , Traina , A. , and Faloutsos , C . 2001. Similarity search without tears: The omni family of all-purpose access methods . In Proceedings of the International Conference on Data Engineering. 623--630 .]] Filho, R. F. S., Traina, A., and Faloutsos, C. 2001. Similarity search without tears: The omni family of all-purpose access methods. In Proceedings of the International Conference on Data Engineering. 623--630.]]"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the International Conference on Very Large Databases. 429--440","author":"Goldstein J.","unstructured":"Goldstein , J. and Ramakrishnan , R . 2000. Contrast plots and p-sphere trees: space vs. time in nearest neighbor searches . In Proceedings of the International Conference on Very Large Databases. 429--440 .]] Goldstein, J. and Ramakrishnan, R. 2000. Contrast plots and p-sphere trees: space vs. time in nearest neighbor searches. In Proceedings of the International Conference on Very Large Databases. 429--440.]]"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/276304.276312"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/602259.602266"},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","unstructured":"Jagadish H. Ooi B. C. Tan K.-L. Yu C. and Zhang R. 2004. iDistance: An adaptive B&plus;-tree based indexing method for nearest neighbor search. Tech. Rep. www.comp.nus.edu.sg\/~ooibc National University of Singapore.]]  Jagadish H. Ooi B. C. Tan K.-L. Yu C. and Zhang R. 2004. iDistance: An adaptive B&plus;-tree based indexing method for nearest neighbor search. Tech. Rep. www.comp.nus.edu.sg\/~ooibc National University of Singapore.]]","DOI":"10.1145\/1071610.1071612"},{"key":"e_1_2_1_22_1","volume-title":"Principle Component Analysis","author":"Jolliffe I. T.","unstructured":"Jolliffe , I. T. 1986. Principle Component Analysis . Springer-Verlag .]] Jolliffe, I. T. 1986. Principle Component Analysis. Springer-Verlag.]]"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/253260.253347"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the International Conference on Very Large Data Bases. 804--815","author":"Koudas N.","unstructured":"Koudas , N. , Ooi , B. C. , Tan , K.-L. , and Zhang , R . 2004. Approximate NN queries on streams with guaranteed error\/performance bounds . In Proceedings of the International Conference on Very Large Data Bases. 804--815 .]] Koudas, N., Ooi, B. C., Tan, K.-L., and Zhang, R. 2004. Approximate NN queries on streams with guaranteed error\/performance bounds. In Proceedings of the International Conference on Very Large Data Bases. 804--815.]]"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1956-0078686-7"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/615204.615210"},{"key":"e_1_2_1_27_1","volume-title":"Fifth Berkeley Symposium on Mathematical statistics and probability","author":"MacQueen J.","year":"1967","unstructured":"MacQueen , J. 1967 . Some methods for classification and analysis of multivariate observations . In Fifth Berkeley Symposium on Mathematical statistics and probability . University of California Press, 281--297.]] MacQueen, J. 1967. Some methods for classification and analysis of multivariate observations. In Fifth Berkeley Symposium on Mathematical statistics and probability. University of California Press, 281--297.]]"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/335168.335219"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the International Conference on Data Engineering.]]","author":"Pagel B.-U.","unstructured":"Pagel , B.-U. , Korn , F. , and Faloutsos , C . 2000. Deflating the dimensionality curse using multiple fractal dimensions . In Proceedings of the International Conference on Data Engineering.]] Pagel, B.-U., Korn, F., and Faloutsos, C. 2000. Deflating the dimensionality curse using multiple fractal dimensions. In Proceedings of the International Conference on Data Engineering.]]"},{"key":"e_1_2_1_30_1","unstructured":"Ramakrishnan R. and Gehrke J. 2000. Database Management Systems. McGraw-Hill.]]   Ramakrishnan R. and Gehrke J. 2000. Database Management Systems. McGraw-Hill.]]"},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the International Conference on Very Large Data Bases. 516--526","author":"Sakurai Y.","unstructured":"Sakurai , Y. , Yoshikawa , M. , and Uemura , S . 2000. The a-tree: An index structure for high-dimensional spaces using relative approximation . In Proceedings of the International Conference on Very Large Data Bases. 516--526 .]] Sakurai, Y., Yoshikawa, M., and Uemura, S. 2000. The a-tree: An index structure for high-dimensional spaces using relative approximation. In Proceedings of the International Conference on Very Large Data Bases. 516--526.]]"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/956863.956881"},{"key":"e_1_2_1_33_1","volume-title":"International Conference on Extending Database Technology","author":"Traina A.","year":"2000","unstructured":"Traina , A. , Seeger , B. , and Faloutsos , C . 2000. Slim-trees: high performance metric trees minimizing overlap between nodes. In Advances in Database Technology---EDBT 2000 , International Conference on Extending Database Technology , Konstanz, Germany, March 27--31 , 2000 , Proceedings. Lecture Notes in Computer Science, vol. 1777. Springer-Verlag, 51--65.]] Traina, A., Seeger, B., and Faloutsos, C. 2000. Slim-trees: high performance metric trees minimizing overlap between nodes. In Advances in Database Technology---EDBT 2000, International Conference on Extending Database Technology, Konstanz, Germany, March 27--31, 2000, Proceedings. Lecture Notes in Computer Science, vol. 1777. Springer-Verlag, 51--65.]]"},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the International Conference on Very Large Data Bases. 194--205","author":"Weber R.","unstructured":"Weber , R. , Schek , H. , and Blott , S . 1998. A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces . In Proceedings of the International Conference on Very Large Data Bases. 194--205 .]] Weber, R., Schek, H., and Blott, S. 1998. A quantitative analysis and performance study for similarity-search methods in high-dimensional spaces. In Proceedings of the International Conference on Very Large Data Bases. 194--205.]]"},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the International Conference on Data Engineering. 516--523","author":"White D.","unstructured":"White , D. and Jain , R . 1996. Similarity indexing with the SS-tree . In Proceedings of the International Conference on Data Engineering. 516--523 .]] White, D. and Jain, R. 1996. Similarity indexing with the SS-tree. In Proceedings of the International Conference on Data Engineering. 516--523.]]"},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of the International Conference on Very Large Data Bases. 421--430","author":"Yu C.","unstructured":"Yu , C. , Ooi , B. C. , Tan , K. L. , and Jagadish , H . 2001. Indexing the distance: an efficient method to knn processing . In Proceedings of the International Conference on Very Large Data Bases. 421--430 .]] Yu, C., Ooi, B. C., Tan, K. L., and Jagadish, H. 2001. Indexing the distance: an efficient method to knn processing. In Proceedings of the International Conference on Very Large Data Bases. 421--430.]]"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/233269.233324"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1071610.1071612","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T16:27:07Z","timestamp":1672244827000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1071610.1071612"}},"subtitle":["An adaptive B\n            <sup>+<\/sup>\n            -tree based indexing method for nearest neighbor search"],"short-title":[],"issued":{"date-parts":[[2005,6]]},"references-count":37,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2005,6]]}},"alternative-id":["10.1145\/1071610.1071612"],"URL":"https:\/\/doi.org\/10.1145\/1071610.1071612","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,6]]},"assertion":[{"value":"2005-06-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}