{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T04:53:21Z","timestamp":1755838401962},"reference-count":29,"publisher":"Institute of Electronics, Information and Communications Engineers (IEICE)","issue":"12","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IEICE Trans. Inf. & Syst."],"published-print":{"date-parts":[[2014]]},"DOI":"10.1587\/transinf.2014edp7108","type":"journal-article","created":{"date-parts":[[2014,11,30]],"date-time":"2014-11-30T23:30:16Z","timestamp":1417390216000},"page":"3142-3154","source":"Crossref","is-referenced-by-count":7,"title":["Efficient K-Nearest Neighbor Graph Construction Using MapReduce for Large-Scale Data Sets"],"prefix":"10.1587","volume":"E97.D","author":[{"given":"Tomohiro","family":"WARASHINA","sequence":"first","affiliation":[{"name":"Nara Institute of Science and Technology"}]},{"given":"Kazuo","family":"AOYAMA","sequence":"additional","affiliation":[{"name":"NTT Communication Science Laboratories, NTT Corporation"}]},{"given":"Hiroshi","family":"SAWADA","sequence":"additional","affiliation":[{"name":"NTT Service Evolution Laboratories, NTT Corporation"}]},{"given":"Takashi","family":"HATTORI","sequence":"additional","affiliation":[{"name":"NTT Communication Science Laboratories, NTT Corporation"}]}],"member":"532","reference":[{"key":"1","doi-asserted-by":"crossref","unstructured":"[1] J. Sankaranarayanan, H. Samet, and A. Varshney, \u201cA fast all nearest neighbor algorithm for applications involving large point-clouds,\u201d Comput. Graph., vol.31, no.2, pp.157-174, April 2007.","DOI":"10.1016\/j.cag.2006.11.011"},{"key":"2","doi-asserted-by":"crossref","unstructured":"[2] M. Connor and P. Kumar, \u201cFast construction of k-nearest neighbor graphs for point clouds,\u201d IEEE Trans. Vis. Comput. Graphics, vol.16, no.4, pp.599-608, 2010.","DOI":"10.1109\/TVCG.2010.9"},{"key":"3","doi-asserted-by":"crossref","unstructured":"[3] A.K. Jain, \u201cData clustering: 50 years beyond K-means,\u201d Pattern Recognit. Lett., vol.31, no.8, pp.651-666, June 2010.","DOI":"10.1016\/j.patrec.2009.09.011"},{"key":"4","doi-asserted-by":"crossref","unstructured":"[4] C.T. Chang, J.Z. Lai, and M. Jeng, \u201cFast agglomerative clustering using information of k-nearest neighbors,\u201d Pattern Recognition, vol.43, no.12, pp.3958-3968, 2010.","DOI":"10.1016\/j.patcog.2010.06.021"},{"key":"5","doi-asserted-by":"crossref","unstructured":"[5] J.B. Tenenbaum, V. de Silva, and J.C. Langford, \u201cA global geometric framework for nonlinear dimensionality reduction,\u201d Science, vol.290, no.5500, pp.2319-2323, Dec. 2000.","DOI":"10.1126\/science.290.5500.2319"},{"key":"6","doi-asserted-by":"crossref","unstructured":"[6] P. Indyk and A. Naor, \u201cNearest-neighbor-preserving embeddings,\u201d ACM Trans. Algorithms, vol.3, no.3, article 31, Aug. 2007.","DOI":"10.1145\/1273340.1273347"},{"key":"7","doi-asserted-by":"crossref","unstructured":"[7] G. Adomavicius and A. Tuzhilin, \u201cToward the next generation of recommender systems: A survey of the state-of-the-art and possible extensions,\u201d IEEE Trans. Knowl. Data Eng., vol.17, no.6, pp.734-749, June 2005.","DOI":"10.1109\/TKDE.2005.99"},{"key":"8","unstructured":"[8] K. Aoyama, K. Saito, H. Sawada, and N. Ueda, \u201cFast approximate similarity search based on degree-reduced neighborhood graphs,\u201d Proc. ACM SIGKDD, pp.1055-1063, 2011."},{"key":"9","doi-asserted-by":"crossref","unstructured":"[9] J. Wang and S. Li, \u201cQuery-driven iterated neighborhood graph search for large scale indexing,\u201d Proc. ACM Multimedia, pp.179-188, 2012.","DOI":"10.1145\/2393347.2393378"},{"key":"10","doi-asserted-by":"crossref","unstructured":"[10] R. Paredes, E. Ch\u00e1vez, K. Figueroa, and G. Navarro, \u201cPractical construction of k-nearest neighbor graphs in metric spaces,\u201d Proc. Int. Workshop Experimental Algorithms, pp.85-97, 2006.","DOI":"10.1007\/11764298_8"},{"key":"11","unstructured":"[11] Y. Chen and J. Patel, \u201cEfficient evaluation of all-nearest-neighbor queries,\u201d Proc. IEEE ICDE, pp.1056-1065, 2007."},{"key":"12","unstructured":"[12] J. Chen, H. Fang, and Y. Saad, \u201cFast approximate kNN graph construction for high dimensional data via recursive Lanczos bisection,\u201d JMLR, vol.10, pp.1989-2012, Dec. 2009."},{"key":"13","doi-asserted-by":"crossref","unstructured":"[13] P.W. Jones, A. Osipov, and V. Rokhlin, \u201cRandomized approximate nearest neighbors algorithm,\u201d Proc. Natl. Acad. Sci., vol.108, no.38, pp.15679-15686, 2011.","DOI":"10.1073\/pnas.1107769108"},{"key":"14","unstructured":"[14] J. Wang, J. Wang, G. Zeng, Z. Tu, R. Gan, and S. Li, \u201cScalable k-NN graph construction for visual descriptors,\u201d Proc. IEEE CVPR, pp.1106-1113, 2012."},{"key":"15","doi-asserted-by":"crossref","unstructured":"[15] W. Dong, C. Moses, and K. Li, \u201cEfficient k-nearest neighbor graph construction for generic similarity measures,\u201d Proc. WWW Conf., pp.577-586, 2011.","DOI":"10.1145\/1963405.1963487"},{"key":"16","doi-asserted-by":"crossref","unstructured":"[16] K.H. Lee, Y.J. Lee, H. Choi, Y.D. Chung, and B. Moon, \u201cParallel data processing with MapReduce: A survey,\u201d Proc. ACM SIGMOD, vol.40, no.4, pp.11-20, Jan. 2012.","DOI":"10.1145\/2094114.2094118"},{"key":"17","doi-asserted-by":"crossref","unstructured":"[17] J. Dean and S. Ghemawat, \u201cMapReduce: Simplified data processing on large clusters,\u201d Commun. ACM, vol.51, no.1, pp.107-113, Jan. 2008.","DOI":"10.1145\/1327452.1327492"},{"key":"18","doi-asserted-by":"crossref","unstructured":"[18] X. Xu, J. J\u00e4ger, and H.P. Kriegel, \u201cA fast parallel clustering algorithm for large spatial databases,\u201d Data Min. Knowl. Discov., vol.3, no.3, pp.263-290, Sept. 1999.","DOI":"10.1023\/A:1009884809343"},{"key":"19","doi-asserted-by":"crossref","unstructured":"[19] D. DeWitt and J. Gray, \u201cParallel database systems: The future of high performance database systems,\u201d Commun. ACM, vol.35, no.6, pp.85-98, June 1992.","DOI":"10.1145\/129888.129894"},{"key":"20","doi-asserted-by":"crossref","unstructured":"[20] R. Vernica, M.J. Carey, and C. Li, \u201cEfficient parallel set-similarity joins using MapReduce,\u201d Proc. ACM SIGMOD, pp.495-506, 2010.","DOI":"10.1145\/1807167.1807222"},{"key":"21","doi-asserted-by":"crossref","unstructured":"[21] W. Zhao, H. Ma, and Q. He, \u201cParallel k-means clustering based on MapReduce,\u201d Proc. IEEE CloudCom, pp.674-679, 2009.","DOI":"10.1007\/978-3-642-10665-1_71"},{"key":"22","unstructured":"[22] W. Lu, Y. Shen, S. Chen, and B.C. Ooi, \u201cEfficient processing of k nearest neighbor joins using MapReduce,\u201d Proc. VLDB Endow., vol.5, no.10, pp.1016-1027, June 2012."},{"key":"23","doi-asserted-by":"crossref","unstructured":"[23] C. Zhang, F. Li, and J. Jestes, \u201cEfficient parallel kNN joins for large data in MapReduce,\u201d Proc. ACM EDBT, pp.38-49, 2012.","DOI":"10.1145\/2247596.2247602"},{"key":"24","unstructured":"[24] B. Bahmani, A. Goel, and R. Shinde, \u201cEfficient distributed locality sensitive hashing,\u201d Proc. ACM CIKM, pp.2174-2178, 2012."},{"key":"25","doi-asserted-by":"crossref","unstructured":"[25] A. Torralba, R. Fergus, and W.T. Freeman, \u201c80 million tiny images: A large data set for nonparametric object and scene recognition,\u201d IEEE Trans. Pattern Anal. Mach. Intell., vol.30, no.11, pp.1958-1970, Nov. 2008.","DOI":"10.1109\/TPAMI.2008.128"},{"key":"26","doi-asserted-by":"crossref","unstructured":"[26] A. Torralba, R. Fergus, and Y. Weiss, \u201cSmall codes and large image databases for recognition,\u201d Proc. IEEE CVPR, pp.1-8, 2008.","DOI":"10.1109\/CVPR.2008.4587633"},{"key":"27","doi-asserted-by":"crossref","unstructured":"[27] D.J. Watts and S.H. Strogatz, \u201cCollective dynamics of \u2018small-world\u2019 networks.,\u201d Nature, vol.393, no.6684, pp.409-410, 1998.","DOI":"10.1038\/30835"},{"key":"28","doi-asserted-by":"crossref","unstructured":"[28] J. Kleinberg, \u201cThe small-world phenomenon: An algorithmic perspective,\u201d Proc. ACM STOC, pp.163-170, 2000.","DOI":"10.1145\/335305.335325"},{"key":"29","doi-asserted-by":"crossref","unstructured":"[29] M. Newman, \u201cThe structure and function of complex networks,\u201d SIAM Review, vol.45, no.2, pp.167-256, 2003.","DOI":"10.1137\/S003614450342480"}],"container-title":["IEICE Transactions on Information and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transinf\/E97.D\/12\/E97.D_2014EDP7108\/_pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,26]],"date-time":"2021-04-26T06:12:08Z","timestamp":1619417528000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transinf\/E97.D\/12\/E97.D_2014EDP7108\/_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"references-count":29,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2014]]}},"URL":"https:\/\/doi.org\/10.1587\/transinf.2014edp7108","relation":{},"ISSN":["0916-8532","1745-1361"],"issn-type":[{"value":"0916-8532","type":"print"},{"value":"1745-1361","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014]]}}}