{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,12]],"date-time":"2026-11-12T15:03:42Z","timestamp":1794495822818,"version":"4.9.1"},"publisher-location":"Cham","reference-count":45,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319149974","type":"print"},{"value":"9783319149981","type":"electronic"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-14998-1_18","type":"book-chapter","created":{"date-parts":[[2015,4,2]],"date-time":"2015-04-02T14:57:00Z","timestamp":1427986620000},"page":"397-417","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Fast Neighborhood Graph Search Using Cartesian Concatenation"],"prefix":"10.1007","author":[{"given":"Jingdong","family":"Wang","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jing","family":"Wang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Gang","family":"Zeng","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rui","family":"Gan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shipeng","family":"Li","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Baining","family":"Guo","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2015,4,1]]},"reference":[{"issue":"1","key":"18_CR1","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1109\/TPAMI.2010.57","volume":"33","author":"H J\u00e9gou","year":"2011","unstructured":"J\u00e9gou H, Douze M, Schmid C (2011) Product quantization for nearest neighbor search. IEEE Trans. Pattern Anal. Mach. Intell. 33(1):117\u2013128","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"issue":"6","key":"18_CR2","doi-asserted-by":"publisher","first-page":"891","DOI":"10.1145\/293347.293348","volume":"45","author":"S Arya","year":"1998","unstructured":"Arya S, Mount DM, Netanyahu NS, Silverman R, Wu AY (1998) An optimal algorithm for approximate nearest neighbor searching in fixed dimensions. J ACM 45(6):891\u2013923","journal-title":"J ACM"},{"key":"18_CR3","unstructured":"Beis JS, Lowe DG (1997) Shape indexing using approximate nearest-neighbour search in high-dimensional spaces. In: Proceedings of CVPR, pp 1000\u20131006"},{"issue":"9","key":"18_CR4","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1145\/361002.361007","volume":"18","author":"JL Bentley","year":"1975","unstructured":"Bentley JL (1975) Multidimensional binary search trees used for associative searching. Commun ACM 18(9):509\u2013517","journal-title":"Commun ACM"},{"issue":"3","key":"18_CR5","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1145\/355744.355745","volume":"3","author":"JH Friedman","year":"1977","unstructured":"Friedman JH, Bentley JL, Finkel RA (1977) An algorithm for finding best matches in logarithmic expected time. ACM Trans Math Softw 3(3):209\u2013226","journal-title":"ACM Trans Math Softw"},{"key":"18_CR6","doi-asserted-by":"crossref","unstructured":"Beygelzimer A, Kakade S, Langford J (2006) Cover trees for nearest neighbor. In: Proceedings of ICML, pp 97\u2013104","DOI":"10.1145\/1143844.1143857"},{"key":"18_CR7","unstructured":"Hwang Y, Han B, Ahn HK (2012) A fast nearest neighbor search algorithm by nonlinear embedding. In: Proceedings of CVPR, pp 3053\u20133060"},{"key":"18_CR8","doi-asserted-by":"crossref","unstructured":"Wang J, Wang J, Zeng G, Gan R, Li S, Guo B (2013) Fast neighborhood graph search using Cartesian concatenation. In: Proceedings of ICCV, pp 2128\u20132135","DOI":"10.1109\/ICCV.2013.265"},{"key":"18_CR9","doi-asserted-by":"crossref","unstructured":"Babenko A, Lempitsky VS (2012) The inverted multi-index. In: Proceedings of CVPR, pp 3069\u20133076","DOI":"10.1109\/CVPR.2012.6248038"},{"issue":"11","key":"18_CR10","doi-asserted-by":"publisher","first-page":"1958","DOI":"10.1109\/TPAMI.2008.128","volume":"30","author":"AB Torralba","year":"2008","unstructured":"Torralba AB, Fergus R, Freeman WT (2008) 80 million tiny images: a large data set for nonparametric object and scene recognition. IEEE Trans. Pattern Anal. Mach. Intell. 30(11):1958\u20131970","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"18_CR11","doi-asserted-by":"crossref","unstructured":"J\u00e9gou H, Tavenard R, Douze M, Amsaleg L (2011) Searching in one billion vectors: re-rank with source coding. In: Proceedings of ICASSP, pp 861\u2013864","DOI":"10.1109\/ICASSP.2011.5946540"},{"key":"18_CR12","doi-asserted-by":"crossref","unstructured":"Dasgupta S, Freund Y (2008) Random projection trees and low dimensional manifolds. In: Proceedings of STOC, pp 537\u2013546","DOI":"10.1145\/1374376.1374452"},{"key":"18_CR13","unstructured":"Liu T, Moore AW, Gray AG, Yang K (2004) An investigation of practical approximate nearest neighbor algorithms. In: Proceedings of NIPS, pp 825\u2013832"},{"key":"18_CR14","unstructured":"Moore AW (2000) The anchors hierarchy: using the triangle inequality to survive high dimensional data. In: Proceedings of UAI, pp 397\u2013405"},{"key":"18_CR15","unstructured":"Yianilos PN (1993) Data structures and algorithms for nearest neighbor search in general metric spaces. In: Proceedings of SODA, pp 311\u2013321"},{"key":"18_CR16","doi-asserted-by":"crossref","unstructured":"Nist\u00e9r D, Stew\u00e9nius H (2006) Scalable recognition with a vocabulary tree. In: Proceedings of CVPR, vol 2, pp 2161\u20132168","DOI":"10.1109\/CVPR.2006.264"},{"key":"18_CR17","doi-asserted-by":"crossref","unstructured":"Jia Y, Wang J, Zeng G, Zha H, Hua XS (2010) Optimizing kd-trees for scalable visual descriptor indexing. In: Proceedings of CVPR, pp 3392\u20133399","DOI":"10.1109\/CVPR.2010.5540006"},{"key":"18_CR18","doi-asserted-by":"crossref","unstructured":"Silpa-Anan C, Hartley R (2008) Optimised kd-trees for fast image descriptor matching. In: Proceedings of CVPR, pp 1\u20138","DOI":"10.1109\/CVPR.2008.4587638"},{"issue":"2","key":"18_CR19","doi-asserted-by":"publisher","first-page":"388","DOI":"10.1109\/TPAMI.2013.125","volume":"36","author":"J Wang","year":"2013","unstructured":"Wang J, Wang N, Jia Y, Li J, Zeng G, Zha H, Hua XS (2013) Trinary-projection trees for approximate nearest neighbor search. IEEE Trans. Pattern Anal. Mach. Intell. 36(2):388\u2013403","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"18_CR20","first-page":"331","volume":"1","author":"M Muja","year":"2009","unstructured":"Muja M, Lowe DG (2009) Fast approximate nearest neighbors with automatic algorithm configuration. VISSAPP 1:331\u2013340","journal-title":"VISSAPP"},{"key":"18_CR21","doi-asserted-by":"crossref","unstructured":"Aoyama K, Saito K, Sawada H, Ueda N (2011) Fast approximate similarity search based on degree-reduced neighborhood graphs. In: Proceedings of KDD, pp 1055\u20131063","DOI":"10.1145\/2020408.2020576"},{"key":"18_CR22","unstructured":"Arya S, Mount DM (1993) Approximate nearest neighbor queries in fixed dimensions. In: Proceedings of SODA, pp 271\u2013280"},{"key":"18_CR23","unstructured":"Hajebi K, Abbasi-Yadkori Y, Shahbazi H, Zhang H (2011) Fast approximate nearest-neighbor search with k-nearest neighbor graph. In: Proceedings of IJCAI, pp 1312\u20131317"},{"key":"18_CR24","volume-title":"Foundations of multidimensional and metric data structures","author":"H Samet","year":"2006","unstructured":"Samet H (2006) Foundations of multidimensional and metric data structures. Elsevier, Amsterdam"},{"key":"18_CR25","unstructured":"Sebastian TB, Kimia BB (2002) Metric-based shape retrieval in large databases. In: Proceedings of ICPR, vol 3, pp 291\u2013296"},{"key":"18_CR26","doi-asserted-by":"crossref","unstructured":"Wang J, Li S (2012) Query-driven iterated neighborhood graph search for large scale indexing. In: Proceedings of ACM multimedia, pp 179\u2013188","DOI":"10.1145\/2393347.2393378"},{"key":"18_CR27","doi-asserted-by":"crossref","unstructured":"Datar M, Immorlica N, Indyk P, Mirrokni VS (2004) Locality-sensitive hashing scheme based on p-stable distributions. In: Proceedings of symposium on computational geometry, pp 253\u2013262","DOI":"10.1145\/997817.997857"},{"key":"18_CR28","unstructured":"Lv Q, Josephson W, Wang Z, Charikar M, Li K (2007) Multi-probe lSH: Efficient indexing for high-dimensional similarity search. In: Proceedings of VLDB, pp 950\u2013961"},{"key":"18_CR29","doi-asserted-by":"crossref","unstructured":"He J, Liu W, Chang SF (2010) Scalable similarity search with optimized kernel hashing. In: Proceedings of KDD, pp 1129\u20131138","DOI":"10.1145\/1835804.1835946"},{"key":"18_CR30","doi-asserted-by":"crossref","unstructured":"Jain P, Kulis B, Grauman K (2008) Fast image search for learned metrics. In: Proceedings of CVPR","DOI":"10.1109\/CVPR.2008.4587841"},{"key":"18_CR31","unstructured":"Kulis B, Darrells T (2009) Learning to hash with binary reconstructive embeddings. In: Proceedigs of NIPS, pp 577\u2013584"},{"key":"18_CR32","doi-asserted-by":"crossref","unstructured":"Kulis B, Grauman K (2009) Kernelized locality-sensitive hashing for scalable image search. In: Proceedings of ICCV, pp 2130\u20132137","DOI":"10.1109\/ICCV.2009.5459466"},{"key":"18_CR33","unstructured":"Raginsky M, Lazebnik S (2009) Locality sensitive binary codes from shift-invariant kernels. In: Proceedings of NIPS"},{"key":"18_CR34","doi-asserted-by":"crossref","unstructured":"Wang J, Kumar S, Chang SF (2010) Semi-supervised hashing for scalable image retrieval. In: Proceedings of CVPR, pp 3424\u20133431","DOI":"10.1109\/CVPR.2010.5539994"},{"key":"18_CR35","first-page":"340","volume":"5","author":"Y Weiss","year":"2012","unstructured":"Weiss Y, Fergus R, Torralba A (2012) Multidimensional spectral hashing. ECCV 5:340\u2013353","journal-title":"ECCV"},{"key":"18_CR36","unstructured":"Weiss Y, Torralba AB, Fergus R (2008) Spectral hashing. In: Proceedings of NIPS, pp 1753\u20131760"},{"key":"18_CR37","doi-asserted-by":"crossref","unstructured":"Gong Y, Lazebnik S (2011) Iterative quantization: a procrustean approach to learning binary codes. In: Proceedings of CVPR, pp 817\u2013824","DOI":"10.1109\/CVPR.2011.5995432"},{"key":"18_CR38","unstructured":"Xu H, Wang J, Li Z, Zeng G, Li S, Yu N (2011) Complementary hashing for approximate nearest neighbor search. In: Proceedings of ICCV, pp 1631\u20131638"},{"key":"18_CR39","doi-asserted-by":"crossref","unstructured":"Wang J, Wang J, Yu N, Li S (2013) Order preserving hashing for approximate nearest neighbor search. In: Proceedings of ACM multimedia, pp 133\u2013142","DOI":"10.1145\/2502081.2502100"},{"issue":"4","key":"18_CR40","doi-asserted-by":"publisher","first-page":"591","DOI":"10.1109\/TPAMI.2008.111","volume":"31","author":"J Sivic","year":"2009","unstructured":"Sivic J, Zisserman A (2009) Efficient visual search of videos cast as text retrieval. IEEE Trans. Pattern Anal. Mach. Intell. 31(4):591\u2013606","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"18_CR41","doi-asserted-by":"crossref","unstructured":"Wang J, Wang J, Hua XS, Li S (2012) Scalable similar image search by joint indices. In: Proceedings of ACM multimedia, pp 1325\u20131326","DOI":"10.1145\/2393347.2396466"},{"key":"18_CR42","doi-asserted-by":"crossref","unstructured":"Tu W, Pan R, Wang J (2012) Similar image search with a tiny bag-of-delegates representation. In: Proceedings of ACM multimedia, pp 885\u2013888","DOI":"10.1145\/2393347.2396338"},{"key":"18_CR43","unstructured":"Fei-Fei L, Fergus R, Perona P (2004) Learning generative visual models from few training examples: an incremental Bayesian approach tested on 101 object categories. In: CVPR 2004 workshop on generative-model based vision"},{"key":"18_CR44","doi-asserted-by":"crossref","unstructured":"Wang J, Wang J, Zeng G, Tu Z, Gan R, Li S (2012) Scalable k-NN graph construction for visual descriptors. In: Proceedings of CVPR, pp 1106\u20131113","DOI":"10.1109\/CVPR.2012.6247790"},{"key":"18_CR45","doi-asserted-by":"crossref","unstructured":"Wang J, Wang J, Ke Q, Zeng G, Li S (2012) Fast approximate k-means via cluster closures. In: Proceedings of CVPR, pp 3037\u20133044","DOI":"10.1109\/CVPR.2012.6248034"}],"container-title":["Multimedia Data Mining and Analytics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-14998-1_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,5]],"date-time":"2024-08-05T11:56:45Z","timestamp":1722859005000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-14998-1_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319149974","9783319149981"],"references-count":45,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-14998-1_18","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/978-3-319-14998-1","asserted-by":"object"}]},"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"1 April 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}