Efficient K-Nearest Neighbor Graph Construction Using MapReduce for Large-Scale Data Sets

Tomohiro WARASHINA  Kazuo AOYAMA  Hiroshi SAWADA  Takashi HATTORI  

IEICE TRANSACTIONS on Information and Systems   Vol.E97-D   No.12   pp.3142-3154
Publication Date: 2014/12/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2014EDP7108
Type of Manuscript: PAPER
Category: Data Engineering, Web Information Systems
k-nearest neighbor graph,  Hadoop MapReduce,  distributed computing,  

Full Text: PDF(1.5MB)>>
Buy this Article

This paper presents an efficient method using Hadoop MapReduce for constructing a K-nearest neighbor graph (K-NNG) from a large-scale data set. K-NNG has been utilized as a data structure for data analysis techniques in various applications. If we are to apply the techniques to a large-scale data set, it is desirable that we develop an efficient K-NNG construction method. We focus on NN-Descent, which is a recently proposed method that efficiently constructs an approximate K-NNG. NN-Descent is implemented on a shared-memory system with OpenMP-based parallelization, and its extension for the Hadoop MapReduce framework is implied for a larger data set such that the shared-memory system is difficult to deal with. However, a simple extension for the Hadoop MapReduce framework is impractical since it requires extremely high system performance because of the high memory consumption and the low data transmission efficiency of MapReduce jobs. The proposed method relaxes the requirement by improving the MapReduce jobs, which employs an appropriate key-value pair format and an efficient sampling strategy. Experiments on large-scale data sets demonstrate that the proposed method both works efficiently and is scalable in terms of a data size, the number of machine nodes, and the graph structural parameter K.