high performance computing on graphics processing units: hgpu.org

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.