Accelerating exact similarity search on CPU-GPU systems

Takazumi Matsumoto; Man Lung Yiu

doi:10.1109/ICDM.2015.125

Accelerating exact similarity search on CPU-GPU systems

Takazumi Matsumoto, Man Lung Yiu

Research output: Chapter in book / Conference proceeding › Conference article published in proceeding or book › Academic research › peer-review

12 Citations (Scopus)

Abstract

In recent years, the use of Graphics Processing Units (GPUs) for data mining tasks has become popular. With modern processors integrating both CPUs and GPUs, it is also important to consider what tasks benefit from GPU processing and which do not, and apply a heterogeneous processing approach to improve the efficiency where applicable. Similarity search, also known as k-nearest neighbor search, is a key part of data mining applications and is used also extensively in applications such as multimedia search, where only a small subset of possible results are used. Our contribution is a new exact kNN algorithm with a compressed partial heapsort that outperforms other state-of-the-art exact kNN algorithms by leveraging both the GPU and CPU.

Original language	English
Title of host publication	Proceedings - 15th IEEE International Conference on Data Mining, ICDM 2015
Publisher	IEEE
Pages	320-329
Number of pages	10
Volume	2016-January
ISBN (Electronic)	9781467395038
DOIs	https://doi.org/10.1109/ICDM.2015.125
Publication status	Published - 5 Jan 2016
Event	15th IEEE International Conference on Data Mining, ICDM 2015 - Atlantic City, United States Duration: 14 Nov 2015 → 17 Nov 2015

Conference

Conference	15th IEEE International Conference on Data Mining, ICDM 2015
Country/Territory	United States
City	Atlantic City
Period	14/11/15 → 17/11/15

Keywords

Data mining
GPU
Heapsort
Heterogeneous processing
Nearest neighbor
Parallel
Similarity search

ASJC Scopus subject areas

General Engineering

More information

10.1109/ICDM.2015.125

http://hdl.handle.net/10397/105723

Cite this

@inproceedings{4d947796af3d4743a501bbabab16484f,

title = "Accelerating exact similarity search on CPU-GPU systems",

abstract = "In recent years, the use of Graphics Processing Units (GPUs) for data mining tasks has become popular. With modern processors integrating both CPUs and GPUs, it is also important to consider what tasks benefit from GPU processing and which do not, and apply a heterogeneous processing approach to improve the efficiency where applicable. Similarity search, also known as k-nearest neighbor search, is a key part of data mining applications and is used also extensively in applications such as multimedia search, where only a small subset of possible results are used. Our contribution is a new exact kNN algorithm with a compressed partial heapsort that outperforms other state-of-the-art exact kNN algorithms by leveraging both the GPU and CPU.",

keywords = "Data mining, GPU, Heapsort, Heterogeneous processing, Nearest neighbor, Parallel, Similarity search",

author = "Takazumi Matsumoto and Yiu, {Man Lung}",

year = "2016",

month = jan,

day = "5",

doi = "10.1109/ICDM.2015.125",

language = "English",

volume = "2016-January",

pages = "320--329",

booktitle = "Proceedings - 15th IEEE International Conference on Data Mining, ICDM 2015",

publisher = "IEEE",

address = "United States",

note = "15th IEEE International Conference on Data Mining, ICDM 2015 ; Conference date: 14-11-2015 Through 17-11-2015",

}

TY - GEN

T1 - Accelerating exact similarity search on CPU-GPU systems

AU - Matsumoto, Takazumi

AU - Yiu, Man Lung

PY - 2016/1/5

Y1 - 2016/1/5

N2 - In recent years, the use of Graphics Processing Units (GPUs) for data mining tasks has become popular. With modern processors integrating both CPUs and GPUs, it is also important to consider what tasks benefit from GPU processing and which do not, and apply a heterogeneous processing approach to improve the efficiency where applicable. Similarity search, also known as k-nearest neighbor search, is a key part of data mining applications and is used also extensively in applications such as multimedia search, where only a small subset of possible results are used. Our contribution is a new exact kNN algorithm with a compressed partial heapsort that outperforms other state-of-the-art exact kNN algorithms by leveraging both the GPU and CPU.

AB - In recent years, the use of Graphics Processing Units (GPUs) for data mining tasks has become popular. With modern processors integrating both CPUs and GPUs, it is also important to consider what tasks benefit from GPU processing and which do not, and apply a heterogeneous processing approach to improve the efficiency where applicable. Similarity search, also known as k-nearest neighbor search, is a key part of data mining applications and is used also extensively in applications such as multimedia search, where only a small subset of possible results are used. Our contribution is a new exact kNN algorithm with a compressed partial heapsort that outperforms other state-of-the-art exact kNN algorithms by leveraging both the GPU and CPU.

KW - Data mining

KW - GPU

KW - Heapsort

KW - Heterogeneous processing

KW - Nearest neighbor

KW - Parallel

KW - Similarity search

UR - http://www.scopus.com/inward/record.url?scp=84963541579&partnerID=8YFLogxK

U2 - 10.1109/ICDM.2015.125

DO - 10.1109/ICDM.2015.125

M3 - Conference article published in proceeding or book

VL - 2016-January

SP - 320

EP - 329

BT - Proceedings - 15th IEEE International Conference on Data Mining, ICDM 2015

PB - IEEE

T2 - 15th IEEE International Conference on Data Mining, ICDM 2015

Y2 - 14 November 2015 through 17 November 2015

ER -

Accelerating exact similarity search on CPU-GPU systems

Abstract

Conference

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this