{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,15]],"date-time":"2026-07-15T07:16:51Z","timestamp":1784099811180,"version":"3.55.0"},"reference-count":47,"publisher":"Association for Computing Machinery (ACM)","issue":"3","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"}],"funder":[{"DOI":"10.13039\/501100002920","name":"Research Grants Council, University Grants Committee, Hong Kong","doi-asserted-by":"publisher","award":["GRF 4161\/07GRF 4173\/08GRF 4169\/09"],"award-info":[{"award-number":["GRF 4161\/07GRF 4173\/08GRF 4169\/09"]}],"id":[{"id":"10.13039\/501100002920","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002920","name":"Research Grants Council, University Grants Committee, Hong Kong","doi-asserted-by":"publisher","award":["DAG07\/08"],"award-info":[{"award-number":["DAG07\/08"]}],"id":[{"id":"10.13039\/501100002920","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004853","name":"Chinese University of Hong Kong","doi-asserted-by":"publisher","award":["2050395"],"award-info":[{"award-number":["2050395"]}],"id":[{"id":"10.13039\/501100004853","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2010,7]]},"abstract":"<jats:p>\n            Nearest Neighbor (NN) search in high-dimensional space is an important problem in many applications. From the database perspective, a good solution needs to have two properties: (i) it can be easily incorporated in a relational database, and (ii) its query cost should increase\n            <jats:italic>sublinearly<\/jats:italic>\n            with the dataset size, regardless of the data and query distributions.\n            <jats:italic>Locality-Sensitive Hashing<\/jats:italic>\n            (LSH) is a well-known methodology fulfilling both requirements, but its current implementations either incur expensive space and query cost, or abandon its theoretical guarantee on the quality of query results.\n          <\/jats:p>\n          <jats:p>\n            Motivated by this, we improve LSH by proposing an access method called the\n            <jats:italic>Locality-Sensitive B-tree<\/jats:italic>\n            (LSB-tree) to enable fast, accurate, high-dimensional NN search in relational databases. The combination of several LSB-trees forms a\n            <jats:italic>LSB-forest<\/jats:italic>\n            that has strong quality guarantees, but improves dramatically the efficiency of the previous LSH implementation having the same guarantees. In practice, the LSB-tree itself is also an effective index which consumes linear space, supports efficient updates, and provides accurate query results. In our experiments, the LSB-tree was faster than: (i) iDistance (a famous technique for exact NN search) by two orders of magnitude, and (ii) MedRank (a recent approximate method with nontrivial quality guarantees) by one order of magnitude, and meanwhile returned much better results.\n          <\/jats:p>\n          <jats:p>\n            As a second step, we extend our LSB technique to solve another classic problem, called Closest Pair (CP) search, in high-dimensional space. The long-term challenge for this problem has been to achieve\n            <jats:italic>subquadratic<\/jats:italic>\n            running time at very high dimensionalities, which fails most of the existing solutions. We show that, using a LSB-forest, CP search can be accomplished in (worst-case) time significantly lower than the quadratic complexity, yet still ensuring very good quality. In practice, accurate answers can be found using just two LSB-trees, thus giving a substantial reduction in the space and running time. In our experiments, our technique was faster: (i) than distance browsing (a well-known method for solving the problem exactly) by several orders of magnitude, and (ii) than D-shift (an approximate approach with theoretical guarantees in low-dimensional space) by one order of magnitude, and at the same time, outputs better results.\n          <\/jats:p>","DOI":"10.1145\/1806907.1806912","type":"journal-article","created":{"date-parts":[[2010,8,2]],"date-time":"2010-08-02T13:15:22Z","timestamp":1280754922000},"page":"1-46","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":94,"title":["Efficient and accurate nearest neighbor and closest pair search in high-dimensional space"],"prefix":"10.1145","volume":"35","author":[{"given":"Yufei","family":"Tao","sequence":"first","affiliation":[{"name":"Chinese University of Hong Kong, Sha Tin, Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ke","family":"Yi","sequence":"additional","affiliation":[{"name":"Hong Kong University of Science and Technology, Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Cheng","family":"Sheng","sequence":"additional","affiliation":[{"name":"Chinese University of Hong Kong, Sha Tin, Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Panos","family":"Kalnis","sequence":"additional","affiliation":[{"name":"King Abdullah University of Science and Technology, Thuwal, Saudi Arabia"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2010,7,30]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.49"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/293347.293348"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497441"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060745.1060840"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/93597.98741"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/312129.312236"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the International Conference on Data Engineering (ICDE'00)","author":"Berchtold S.","unstructured":"Berchtold , S. , Bohm , C. , Jagadish , H. V. , Kriegel , H.-P. , and Sander , J . 2000. Independent quantization: An index compression technique for high-dimensional data spaces . In Proceedings of the International Conference on Data Engineering (ICDE'00) . 577--588. Berchtold, S., Bohm, C., Jagadish, H. V., Kriegel, H.-P., and Sander, J. 2000. Independent quantization: An index compression technique for high-dimensional data spaces. In Proceedings of the International Conference on Data Engineering (ICDE'00). 577--588."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.842249"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the International Conference on Database Theory (ICDT'99)","author":"Beyer K. S.","unstructured":"Beyer , K. S. , Goldstein , J. , Ramakrishnan , R. , and Shaft , U. 1999. When is \u201cnearest neighbor\u201d meaningful&quest; In Proceedings of the International Conference on Database Theory (ICDT'99) . 217--235. Beyer, K. S., Goldstein, J., Ramakrishnan, R., and Shaft, U. 1999. When is \u201cnearest neighbor\u201d meaningful&quest; In Proceedings of the International Conference on Database Theory (ICDT'99). 217--235."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/357775.357776"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335388"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509965"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB'99)","author":"Chaudhuri S.","unstructured":"Chaudhuri , S. and Gravano , L . 1999. Evaluating top-k selection queries . In Proceedings of the International Conference on Very Large Databases (VLDB'99) . 397--410. Chaudhuri, S. and Gravano, L. 1999. Evaluating top-k selection queries. In Proceedings of the International Conference on Very Large Databases (VLDB'99). 397--410."},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the Interational Conference on Data Engineering (ICDE'02)","author":"Chen C.-M.","unstructured":"Chen , C.-M. and Ling , Y . 2002. A sampling-based estimator for top-k query . In Proceedings of the Interational Conference on Data Engineering (ICDE'02) . 617--627. Chen, C.-M. and Ling, Y. 2002. A sampling-based estimator for top-k query. In Proceedings of the Interational Conference on Data Engineering (ICDE'02). 617--627."},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the International Conference on Data Engineering (ICDE'00)","author":"Ciaccia P.","unstructured":"Ciaccia , P. and Patella , M . 2000. Pac nearest neighbor queries: Approximate and controlled search in high-dimensional and metric spaces . In Proceedings of the International Conference on Data Engineering (ICDE'00) . 244--255. Ciaccia, P. and Patella, M. 2000. Pac nearest neighbor queries: Approximate and controlled search in high-dimensional and metric spaces. In Proceedings of the International Conference on Data Engineering (ICDE'00). 244--255."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335414"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/997817.997857"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872795"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/375551.375567"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the International Conference on Data Engineering (ICDE'01)","author":"Ferhatosmanoglu H.","unstructured":"Ferhatosmanoglu , H. , Tuncel , E. , Agrawal , D. , and Abbadi , A. E . 2001. Approximate nearest neighbor searching in multimedia databases . In Proceedings of the International Conference on Data Engineering (ICDE'01) . 503--511. Ferhatosmanoglu, H., Tuncel, E., Agrawal, D., and Abbadi, A. E. 2001. Approximate nearest neighbor searching in multimedia databases. In Proceedings of the International Conference on Data Engineering (ICDE'01). 503--511."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/301970.301973"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/280277.280279"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB'99)","author":"Gionis A.","unstructured":"Gionis , A. , Indyk , P. , and Motwani , R . 1999. Similarity search in high dimensions via hashing . In Proceedings of the International Conference on Very Large Databases (VLDB'99) . 518--529. Gionis, A., Indyk, P., and Motwani, R. 1999. Similarity search in high dimensions via hashing. In Proceedings of the International Conference on Very Large Databases (VLDB'99). 518--529."},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB'00)","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 the International Conference on Very Large Databases (VLDB'00) . 429--440. Goldstein, J. and Ramakrishnan, R. 2000. Contrast plots and p-sphere trees: Space vs. time in nearest neighbour searches. In Proceedings of the International Conference on Very Large Databases (VLDB'00). 429--440."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/602259.602266"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/874063.875592"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/276304.276326"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/320248.320255"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2005.66"},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP'04)","author":"Indyk P.","unstructured":"Indyk , P. , Lewenstein , M. , Lipsky , O. , and Porat , E . 2004. Closest pair problems in very high dimensions . In Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP'04) . 782--792. Indyk, P., Lewenstein, M., Lipsky, O., and Porat, E. 2004. Closest pair problems in very high dimensions. In Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP'04). 782--792."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276876"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1071610.1071612"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258653"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.908983"},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the International Conference on Data Engineering (ICDE'04)","author":"Koudas N.","unstructured":"Koudas , N. , Ooi , B. C. , Shen , H. T. , and Tung , A. K. H. 2004. Ldc: Enabling search by partial distance in a hyper-dimensional space . In Proceedings of the International Conference on Data Engineering (ICDE'04) . 6--17. Koudas, N., Ooi, B. C., Shen, H. T., and Tung, A. K. H. 2004. Ldc: Enabling search by partial distance in a hyper-dimensional space. In Proceedings of the International Conference on Data Engineering (ICDE'04). 6--17."},{"key":"e_1_2_1_36_1","volume-title":"Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'04)","author":"Krauthgamer R.","unstructured":"Krauthgamer , R. and Lee , J. R . 2004. Navigating nets: Simple algorithms for proximity search . In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'04) . 798--807. Krauthgamer, R. and Lee, J. R. 2004. Navigating nets: Simple algorithms for proximity search. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'04). 798--807."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1992.267752"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2002.1019214"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/615204.615210"},{"key":"e_1_2_1_40_1","volume-title":"Proceedings of the Canadian Conference on Computational Geometry (CCCG'00)","author":"Lopez M. A.","unstructured":"Lopez , M. A. and Liao , S . 2000. Finding k-closest-pairs efficiently for high dimensional data . In Proceedings of the Canadian Conference on Computational Geometry (CCCG'00) . 197--204. Lopez, M. A. and Liao, S. 2000. Finding k-closest-pairs efficiently for high dimensional data. In Proceedings of the Canadian Conference on Computational Geometry (CCCG'00). 197--204."},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB'07)","author":"Lv Q.","unstructured":"Lv , Q. , Josephson , W. , Wang , Z. , Charikar , M. , and Li , K . 2007. Multi-Probe lsh: Efficient indexing for high-dimensional similarity search . In Proceedings of the International Conference on Very Large Databases (VLDB'07) . 950--961. Lv, Q., Josephson, W., Wang, Z., Charikar, M., and Li, K. 2007. Multi-Probe lsh: Efficient indexing for high-dimensional similarity search. In Proceedings of the International Conference on Very Large Databases (VLDB'07). 950--961."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109688"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/223784.223794"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1975.8"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559905"},{"key":"e_1_2_1_46_1","volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB'98)","author":"Weber R.","unstructured":"Weber , R. , Schek , H.-J. , 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 Databases (VLDB'98) . 194--205. Weber, R., Schek, H.-J., 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 Databases (VLDB'98). 194--205."},{"key":"e_1_2_1_47_1","volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB'07)","author":"Wong R. C.-W.","unstructured":"Wong , R. C.-W. , Tao , Y. , Fu , A. W.-C. , and Xiao , X . 2007. On efficient spatial matching . In Proceedings of the International Conference on Very Large Databases (VLDB'07) . 579--590. Wong, R. C.-W., Tao, Y., Fu, A. W.-C., and Xiao, X. 2007. On efficient spatial matching. In Proceedings of the International Conference on Very Large Databases (VLDB'07). 579--590."}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1806907.1806912","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1806907.1806912","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T11:39:37Z","timestamp":1750246777000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1806907.1806912"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,7]]},"references-count":47,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2010,7]]}},"alternative-id":["10.1145\/1806907.1806912"],"URL":"https:\/\/doi.org\/10.1145\/1806907.1806912","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,7]]},"assertion":[{"value":"2009-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-07-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}