en
Scientific article
English

Employing GPU architectures for permutation-based indexing

Published inMultimedia Tools and Applications, vol. 76, no. 9, p. 11859-11887
Publication date2017
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. 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 summarized our hybrid CPU-GPU solution. Our experience gained from this research may be utilized in other individual problems that require computing Lp distances in high-dimensional spaces, parallel top-k selection, or partial sorting of multiple smaller sets. We also provide guidelines how to balance workload in hybrid CPU-GPU systems.

Keywords
  • GPU
  • Parallel
  • Permutation-based indexing
  • Approximate similarity search
  • Bitonic sorting
Research group
Citation (ISO format)
KRULIŠ, Martin, OSIPYAN, Hasmik, MARCHAND-MAILLET, Stéphane. Employing GPU architectures for permutation-based indexing. In: Multimedia Tools and Applications, 2017, vol. 76, n° 9, p. 11859–11887. doi: 10.1007/s11042-016-3677-7
Main files (1)
Article (Published version)
accessLevelRestricted
Identifiers
ISSN of the journal1380-7501
408views
1downloads

Technical informations

Creation2017/10/03 17:03:00
First validation2017/10/03 17:03:00
Update time2023/03/15 02:06:59
Status update2023/03/15 02:06:59
Last indexation2024/01/17 00:53:21
All rights reserved by Archive ouverte UNIGE and the University of GenevaunigeBlack