Hybrid KNN-join: Parallel nearest neighbor searches exploiting CPU and GPU architectural features

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

K Nearest Neighbor (KNN) joins are used in scientific domains for data analysis, and are building blocks of several well-known algorithms. KNN-joins find the KNN of all points in a dataset. This paper focuses on a hybrid CPU/GPU approach for low-dimensional KNN-joins, where the GPU may not yield substantial performance gains over parallel CPU algorithms. We utilize a work queue that prioritizes computing data points in high density regions on the GPU, and low density regions on the CPU, thereby taking advantage of each architecture's relative strengths. Our approach, HYBRIDKNN-JOIN, effectively augments a state-of-the-art multi-core CPU algorithm. We propose optimizations that (i) maximize GPU query throughput by assigning the GPU large batches of work; (ii) increase workload granularity to optimize GPU utilization; and, (iii) limit load imbalance between CPU and GPU architectures. We compare HYBRIDKNN-JOIN to one GPU and two parallel CPU reference implementations. Compared to the reference implementations, we find that the hybrid algorithm performs best on larger workloads (dataset size and K). The methods employed in this paper show promise for the general division of work in other hybrid algorithms.

Original languageEnglish (US)
Pages (from-to)119-137
Number of pages19
JournalJournal of Parallel and Distributed Computing
Volume149
DOIs
StatePublished - Mar 2021

Keywords

  • GPGPU
  • Heterogeneous systems
  • In-memory database
  • Nearest neighbor search
  • Query optimization

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Networks and Communications
  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'Hybrid KNN-join: Parallel nearest neighbor searches exploiting CPU and GPU architectural features'. Together they form a unique fingerprint.

Cite this