Employing GPU architectures for permutation-based indexing

Kruliš, Martin; Osipyan, Hasmik; Marchand-Maillet, Stéphane

doi:10.1007/s11042-016-3677-7

Scientific article

English

Employing GPU architectures for permutation-based indexing

Contributors

Kruliš, Martin; Osipyan, Hasmik; Marchand-Maillet, Stéphane

Published in

Multimedia Tools and Applications, vol. 76, no. 9, p. 11859-11887

Publication date

2017

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

UNIGE affiliation entities

UNIGE research groups

Viper 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

Article (Published version)

Identifiers

PID : unige:97526
DOI : 10.1007/s11042-016-3677-7

Additional URL for this publication

http://link.springer.com/10.1007/s11042-016-3677-7

Journal ISSN

1380-7501

506views

1downloads

Creation

03/10/2017 17:03:00

First validation

03/10/2017 17:03:00

Update

13/10/2025 19:44:10

Status update

15/03/2023 02:06:59

Last indexation

03/12/2025 07:39:45

Employing GPU architectures for permutation-based indexing

Contributors

Published in

Publication date

Abstract

Keywords

UNIGE affiliation entities

UNIGE research groups

Citation (ISO format)

Main files (1)

Identifiers

Additional URL for this publication

Journal ISSN

Technical informations

Creation

First validation

Update

Status update

Last indexation