Abstract
Permutation-based indexing is one of the most popular techniques for the approximate nearest-neighbor search problem in high-dimensional spaces. Due to the exponential increase of multimedia data, the time required to index this data has become a serious constraint of the indexing techniques.
One of the possible steps towards faster index construction is utilization of massively parallel platforms such as the GPGPU architectures. In this paper, we have focused on two particular steps of permutation index construction -- the selection of top-k nearest pivot points and sorting these pivots according to their respective distances.
Even though these steps are integrated into a more complex algorithm, we address them selectively since they may be employed individually for different indexing techniques or query processing algorithms in multimedia databases. We also provide a discussion of alternative approaches that we have tested but which have proved less efficient on present hardware.