Connor, M.Kumar, P.Hans-Christian Hege and David Laidlaw and Renato Pajarola and Oliver Staadt2014-01-292014-01-292008978-3-905674-12-51727-8376https://doi.org/10.2312/VG/VG-PBG08/025-031We present a parallel algorithm for k-nearest neighbor graph construction that uses Morton ordering. Experiments show that our approach has the following advantages over existing methods: (1) Faster construction of k-nearest neighbor graphs in practice on multi-core machines. (2) Less space usage. (3) Better cache efficiency. (4) Ability to handle large data sets. (5) Ease of parallelization and implementation.Categories and Subject Descriptors (according to ACM CCS): I.3.5 [Computer Graphics]: k-NN Graphs