Parallel Construction of k-Nearest Neighbor Graphs for Point Clouds

Connor, M.; Kumar, P.

Parallel Construction of k-Nearest Neighbor Graphs for Point Clouds

Files

025-031.pdf (379.38 KB)

Date

2008

Authors

Connor, M.
Kumar, P.

Publisher

The Eurographics Association

Abstract

We 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.

        @inproceedings{10.2312:VG/VG-PBG08/025-031
,
booktitle = {IEEE/ EG Symposium on Volume and Point-Based Graphics
},
editor = {Hans-Christian Hege and David Laidlaw and Renato Pajarola and Oliver Staadt
},
title = {{Parallel Construction of k-Nearest Neighbor Graphs for Point Clouds
}},
author = {Connor, M. and 
Kumar, P.
},
year = {2008
},
publisher = {The Eurographics Association
},
ISSN = {1727-8376
},
ISBN = {978-3-905674-12-5
},
DOI = {10.2312/VG/VG-PBG08/025-031
}
}