{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,23]],"date-time":"2025-04-23T17:26:57Z","timestamp":1745429217568,"version":"3.40.3"},"publisher-location":"Cham","reference-count":32,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319250861"},{"type":"electronic","value":"9783319250878"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-25087-8_7","type":"book-chapter","created":{"date-parts":[[2015,10,6]],"date-time":"2015-10-06T14:11:35Z","timestamp":1444140695000},"page":"77-89","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["Faster Dual-Tree Traversal for Nearest Neighbor Search"],"prefix":"10.1007","author":[{"given":"Ryan R.","family":"Curtin","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,10,17]]},"reference":[{"key":"7_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1007\/978-3-540-88688-4_27","volume-title":"Computer Vision \u2013 ECCV 2008","author":"N Kumar","year":"2008","unstructured":"Kumar, N., Zhang, L., Nayar, S.K.: What is a good nearest neighbors algorithm for finding similar patches in images? In: Forsyth, D., Torr, P., Zisserman, A. (eds.) ECCV 2008, Part II. LNCS, vol. 5303, pp. 364\u2013378. Springer, Heidelberg (2008)"},{"key":"7_CR2","unstructured":"Koren, Y.: The BellKor solution to the Netflix Grand Prize (2009)"},{"key":"7_CR3","unstructured":"Cunningham, P., Delany, S.J.: k-nearest neighbour classifiers. Technical Report UCD-CSI-2007-4, University College Dublin (2007)"},{"key":"7_CR4","unstructured":"Weinberger, K.Q., Blitzer, J., Saul, L.K.: Distance metric learning for large margin nearest neighbor classification. In: Advances in Neural Information Processing Systems 18 (NIPS 2005), pp. 1473\u20131480 (2005)"},{"issue":"9","key":"7_CR5","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1145\/361002.361007","volume":"18","author":"JL Bentley","year":"1975","unstructured":"Bentley, J.L.: Multidimensional binary search trees used for associative searching. Communications of the ACM 18(9), 509\u2013517 (1975)","journal-title":"Communications of the ACM"},{"issue":"7","key":"7_CR6","doi-asserted-by":"publisher","first-page":"750","DOI":"10.1109\/T-C.1975.224297","volume":"100","author":"K Fukunaga","year":"1975","unstructured":"Fukunaga, K., Narendra, P.M.: A branch and bound algorithm for computing k-nearest neighbors. IEEE Transactions on Computers 100(7), 750\u2013753 (1975)","journal-title":"IEEE Transactions on Computers"},{"issue":"1","key":"7_CR7","doi-asserted-by":"publisher","first-page":"63","DOI":"10.1007\/PL00009449","volume":"22","author":"KL Clarkson","year":"1999","unstructured":"Clarkson, K.L.: Nearest neighbor queries in metric spaces. Discrete & Computational Geometry 22(1), 63\u201393 (1999)","journal-title":"Discrete & Computational Geometry"},{"key":"7_CR8","doi-asserted-by":"crossref","unstructured":"Andoni, A., Indyk, P.: Near-optimal hashing algorithms for approximate nearest neighbor in high dimensions. In: Forty-Seventh Annual IEEE Symposium of Foundations of Computer Science (FOCS 2006), pp. 459\u2013468. IEEE (2006)","DOI":"10.1109\/FOCS.2006.49"},{"key":"7_CR9","doi-asserted-by":"crossref","unstructured":"Indyk, P., Motwani, R.: Approximate nearest neighbors: towards removing the curse of dimensionality. In: Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing (STOC 1998), pp. 604\u2013613. ACM (1998)","DOI":"10.1145\/276698.276876"},{"key":"7_CR10","doi-asserted-by":"crossref","unstructured":"Datar, M., Immorlica, N., Indyk, P., Mirrokni, V.S.: Locality-sensitive hashing scheme based on p-stable distributions. In: Proceedings of the Twentieth Annual Symposium on Computational Geometry (SoCG 2004), pp. 253\u2013262. ACM (2004)","DOI":"10.1145\/997817.997857"},{"key":"7_CR11","unstructured":"Gray, A.G., Moore, A.W.: \u2018N-Body\u2019 problems in statistical learning. In: Advances in Neural Information Processing Systems, vol. 14, no. 4, pp. 521\u2013527 (2001)"},{"key":"7_CR12","unstructured":"Curtin, R.R., March, W.B., Ram, P., Anderson, D.V., Gray, A.G., Isbell Jr., C.L.: Tree-independent dual-tree algorithms. In: Proceedings of the 30th International Conference on Machine Learning (ICML 2013) (2013)"},{"key":"7_CR13","unstructured":"Ram, P., Lee, D., March, W.B., Gray, A.G.: Linear-time algorithms for pairwise statistical problems. In: Advances in Neural Information Processing Systems, vol. 22 (2009)"},{"key":"7_CR14","unstructured":"Curtin, R.R., Lee, D., March, W.B., Ram, P.: Plug-and-play runtime analysis for dual-tree algorithms. The Journal of Machine Learning Research (2015)"},{"key":"7_CR15","doi-asserted-by":"crossref","unstructured":"Gray, A.G., Moore, A.W.: Nonparametric density estimation: toward computational tractability. In: Proceedings of the 3rd SIAM International Conference on Data Mining (SDM 2003), San Francisco, pp. 203\u2013211 (2003)","DOI":"10.1137\/1.9781611972733.19"},{"key":"7_CR16","doi-asserted-by":"crossref","unstructured":"March, W.B., Ram, P., Gray, A.G.: Fast Euclidean minimum spanning tree: algorithm, analysis, and applications. In: Proceedings of the 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD 2010), Washington, D.C., pp. 603\u2013612 (2010)","DOI":"10.1145\/1835804.1835882"},{"key":"7_CR17","unstructured":"Wang, P., Lee, D., Gray, A.G., Rehg, J.M.: Fast mean shift with accurate and stable convergence. In: Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics (AISTATS 2007), pp. 604\u2013611 (2007)"},{"key":"7_CR18","unstructured":"Lee, D., Gray, A.G.: Faster gaussian summation: theory and experiment. In: Proceedings of the 22nd Conference on Uncertainty in Artificial Intelligence (2006)"},{"key":"7_CR19","doi-asserted-by":"crossref","unstructured":"Curtin, R.R., Ram, P., Gray, A.G.: Fast exact max-kernel search. In: SIAM International Conference on Data Mining (SDM 2013), pp. 1\u20139 (2013)","DOI":"10.1137\/1.9781611972832.1"},{"key":"7_CR20","doi-asserted-by":"crossref","unstructured":"Klaas, M., Briers, M., De Freitas, N., Doucet, A., Maskell, S., Lang, D.: Fast particle smoothing: if I had a million particles. In: Proceedings of the 23rd International Conference on Machine Learning (ICML 2006), pp. 25\u201329 (2006)","DOI":"10.1145\/1143844.1143905"},{"issue":"1","key":"7_CR21","first-page":"3221","volume":"15","author":"L Maaten Van Der","year":"2014","unstructured":"Van Der Maaten, L.: Accelerating t-sne using tree-based algorithms. The Journal of Machine Learning Research 15(1), 3221\u20133245 (2014)","journal-title":"The Journal of Machine Learning Research"},{"key":"7_CR22","unstructured":"Moore, D.A., Russell, S.J.: Fast Gaussian process posteriors with product trees. In: Proceedings of the Thirtieth Conference on Uncertainty in Artificial Intelligence (UAI 2014), Quebec City, July 2014"},{"issue":"4","key":"7_CR23","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1002\/sam.11218","volume":"7","author":"RR Curtin","year":"2014","unstructured":"Curtin, R.R., Ram, P.: Dual-tree fast exact max-kernel search. Statistical Analysis and Data Mining 7(4), 229\u2013253 (2014)","journal-title":"Statistical Analysis and Data Mining"},{"key":"7_CR24","unstructured":"Liu, T., Moore, A.W., Yang, K., Gray, A.G.: An investigation of practical approximate nearest neighbor algorithms. In: Advances in Neural Information Processing Systems 17 (NIPS 2004), pp. 825\u2013832 (2004)"},{"key":"7_CR25","first-page":"801","volume":"14","author":"RR Curtin","year":"2013","unstructured":"Curtin, R.R., Cline, J.R., Slagle, N.P., March, W.B., Ram, P., Mehta, N.A., Gray, A.G.: mlpack: A scalable C++ machine learning library. Journal of Machine Learning Research 14, 801\u2013805 (2013)","journal-title":"Journal of Machine Learning Research"},{"key":"7_CR26","unstructured":"Lichman, M.: UCI machine learning repository (2013)"},{"issue":"2","key":"7_CR27","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1023\/A:1009783824328","volume":"1","author":"T Zhang","year":"1997","unstructured":"Zhang, T., Ramakrishnan, R., Livny, M.: BIRCH: A new data clustering algorithm and its applications. Data Mining and Knowledge Discovery 1(2), 141\u2013182 (1997)","journal-title":"Data Mining and Knowledge Discovery"},{"key":"7_CR28","doi-asserted-by":"crossref","unstructured":"Lupton, R., Gunn, J.E., Ivezic, Z., Knapp, G.R., Kent, S.: The SDSS imaging pipelines. In: Astronomical Data Analysis Software and Systems X, vol. 238, p. 269 (2001)","DOI":"10.1117\/12.457307"},{"issue":"2","key":"7_CR29","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1086\/524984","volume":"175","author":"JK Adelman-McCarthy","year":"2008","unstructured":"Adelman-McCarthy, J.K., Ag\u00fceros, M.A., Allam, S.S., Prieto, C.A., Anderson, K.S.J., et al.: The sixth data release of the Sloan Digital Sky Survey. The Astrophysical Journal Supplement Series 175(2), 297 (2008)","journal-title":"The Astrophysical Journal Supplement Series"},{"key":"7_CR30","doi-asserted-by":"crossref","unstructured":"Dong, W., Wang, Z., Josephson, W.K., Charikar, M., Li, K.: Modeling LSH for performance tuning. In: Proceedings of the 17th ACM Conference on Information and Knowledge Management (CIKM 2008), pp. 669\u2013678. ACM (2008)","DOI":"10.1145\/1458082.1458172"},{"key":"7_CR31","unstructured":"Dong, W.: Personal communication (2015)"},{"key":"7_CR32","unstructured":"Moore, A.W.: The anchors hierarchy: using the triangle inequality to survive high dimensional data. In: Proceedings of the Sixteenth Conference on Uncertainty in Artificial Intelligence (UAI 2000), pp. 397\u2013405 (2000)"}],"container-title":["Lecture Notes in Computer Science","Similarity Search and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-25087-8_7","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,30]],"date-time":"2019-05-30T23:59:05Z","timestamp":1559260745000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-25087-8_7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319250861","9783319250878"],"references-count":32,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-25087-8_7","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"17 October 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}