Improving data-parallel construction of δN-nets with maximum dispersion
Peter Zinterhof · 2014
Linear nearest-neighbor search in high-dimensional data exposes high computational complexity. In order to minimize search complexity we employ optimal δN-nets of rank N, which consist of a sub set of N vectors out of an initial code book E, yet approximate all En vectors of E by the least error (denoted by the number theoretical concept of dispersion) of all possible selections of N vectors. In this paper we demonstrate a substantially improved algorithm, which results in a reduction of computational complexity from previously O (En NΛ2- NΛ3) to O(EnΛ2). We demonstrate computational feasibility both on CPU-and GPGPU-based systems for any desired accuracy in the approximation of codebook E by some δN-net for real-world problem sizes in the range of En = [10Λ7..10Λ8]. In addition to the high speedup that can be achieved by the new algorithm, the GPGPU implementation typically shows speedups of one order of magnitude over a CPU implementation. We also give a practical example of image segmentation within computed tomography scans in order to show one potential application of this new approach.