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 analyzed the computational costs of individual steps of the permutation-based index construction in a high-dimensional feature space and proposed a hybrid solution, where computational power of GPU is utilized for distance computations whilst the host CPU performs the postprocessing and sorting steps. Despite the fact that computing the distances is a naturally data-parallel task, an efficient implementation is quite challenging due to various GPU limitations and complex memory hierarchy. We have tested possible approaches to work division and data caching to utilize the GPU to its best abilities. We summarize our empirical results and point out the optimal solution. |
Year | DOI | Venue |
---|---|---|
2015 | 10.1109/CBMI.2015.7153619 | 2015 13th International Workshop on Content-Based Multimedia Indexing (CBMI) |
Keywords | Field | DocType |
permutation based indexing,high dimensional data,approximate nearest-neighbor search problem,high-dimensional spaces,multimedia data,indexing techniques,massively parallel platforms,GPGPU architectures,computational costs,permutation-based index construction,high-dimensional feature space,distance computations,host CPU,postprocessing steps,sorting steps,data-parallel task | Clustering high-dimensional data,Memory hierarchy,Massively parallel,Computer science,Permutation,Parallel computing,Search engine indexing,Sorting,General-purpose computing on graphics processing units,Search problem | Conference |
ISSN | Citations | PageRank |
1949-3983 | 2 | 0.41 |
References | Authors | |
9 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Martin Krulis | 1 | 76 | 13.27 |
Hasmik Osipyan | 2 | 11 | 2.65 |
Stéphane Marchand-Maillet | 3 | 1039 | 104.97 |