This thesis presents an efficient method using Hadoop MapReduce for constructing %an approximate a K-nearest neighbor graph (K-NNG) from a large-scale data set. A K-NNG has been utilized as a data structure for data analysis techniques in various applications. To apply the techniques to a large-scale data set, developing an efficient K-NNG construction method is desired. We focus on NN-Descent, which is a recently proposed versatile method that efficiently constructs an approximate K-NNG without limits on a data type nor a defined dissimilarity. NN-Descent is implemented on a shared-memory system with OpenMP-based parallelization. For a larger data set beyond a data size that the shared-memory system can deal with, NN-Descent may be simply extended for the Hadoop MapReduce framework. However, due to high memory consumption and low data transmission efficiency in MapReduce jobs, extremely high system performance is required to apply the extended NN-Descent in practice. The proposed method lowers the requirement by improving the data structure and the algorithm of the MapReduce jobs. The proposed method uses appropriate formats of key-value pairs and an efficient sampling strategy. Experimental results on a large-scale data set demonstrate that the proposed method does not only work efficiently but also is scalable for a data size, the number of machine nodes, and graph structural parameter K.
K 近傍グラフは，大規模データを取り扱う幅広い技術分野で利用されているため， 大規模データを対象とした K 近傍グラフを効率良く構築することは重要である. 本稿では，データの種類や非類似度に対して制約を課さずに，効率良く K 近傍グラフを構築する発見的方法である NN-Descent 法に着目し，この方法の効率的な MapReduce 実装法とその改良アルゴリズムとを提案する． NN-Descent 法には，OpenMP を用いた並列実装法があり， 共有メモリを有する計算機環境で容易に分散処理を行うことが可能である. また，MapReduce フレームワークへの拡張法もあり， 大規模データに適用可能であることが示唆されている. しかしながら，この MapReduce 拡張法には，メモリ使用量とデータ転送量とが共に大きいという問題があり， 実際に，大規模データに適用することは困難である. 提案法は，少メモリ使用量と少データ転送量とを同時に実現するように設計された Map 関数， Reduce 関数及びそれらの入出力である key-value ペアと，効率的な sampling 法とを用いて， 上記問題の緩和を可能にする. 大規模実データを用いた評価実験では，データサイズ，処理を行う計算機の数，及びパラメータ K に着目して， 提案法のスケーラビリティの評価を行った． 別の評価実験では，提案法が，上記 MapReduce 拡張法よりも効率良く処理を行えることを確認した. 提案法を用いることにより，大規模 K 近傍グラフを効率良く構築することが可能になる.