Data-Parallel Construction of delta_N-Nets with Maximum Dispersion

Peter Zinterhof
Salzburg University, Austria
Parallel Numerics, 2011


   title={Data-Parallel Construction of $delta$N-Nets with Maximum Dispersion},

   author={Zinterhof, P.},

   journal={ParNum 11},




Download Download (PDF)   View View   Source Source   



Linear nearest-neighbor search in high-dimensional data exposes high computational complexity. In order to minimize search complexity we employ optimal delta-nets of rank N, which consist of a small sub set of N vectors out of an initial code book E, yet approximate all En vectors of E by the least error of all possible selections of N vectors. By employing a distributed, data-parallel approach which can be computed efficiently on a cluster of GPUs, we observe speedup factors up to 215, compared to a sequential CPUbased solution. Despite the construction process for a suitable delta-net being of complexity O(EnN^2 – N^3), our algorithm makes computation of quasi-optimal delta-nets feasible with respect to our sample application of principal component analysis (PCA)-based feature detection.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: