HEGJoin: Heterogeneous CPU-GPU Epsilon Grids for Accelerated Distance Similarity Join

Benoit Gallet, Michael Gowanlock

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

The distance similarity join operation joins two datasets (or tables), A and B, based on a search distance, and returns the pairs of points such that the distance between. In the case where, then this operation is a similarity self-join (and therefore,. In contrast to the majority of the literature that focuses on either the CPU or the GPU, we propose in this paper Heterogeneous CPU-GPU Epsilon Grids Join (HEGJoin), an efficient algorithm to process a distance similarity join using both the CPU and the GPU. We leverage two state-of-the-art algorithms: LBJoin for the GPU and Super-EGO for the CPU. We achieve good load balancing between architectures by assigning points with larger workloads to the GPU and those with lighter workloads to the CPU through the use of a shared work queue. We examine the performance of our heterogeneous algorithm against LBJoin, as well as Super-EGO by comparing performance to the upper bound throughput. We observe that HEGJoin consistently achieves close to this upper bound.

Original languageEnglish (US)
Title of host publicationDatabase Systems for Advanced Applications - 25th International Conference, DASFAA 2020, Proceedings
EditorsYunmook Nah, Bin Cui, Sang-Won Lee, Jeffrey Xu Yu, Yang-Sae Moon, Steven Euijong Whang
PublisherSpringer Science and Business Media Deutschland GmbH
Pages372-388
Number of pages17
ISBN (Print)9783030594183
DOIs
StatePublished - 2020
Externally publishedYes
Event25th International Conference on Database Systems for Advanced Applications, DASFAA 2020 - Jeju, Korea, Republic of
Duration: Sep 24 2020Sep 27 2020

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12114 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference25th International Conference on Database Systems for Advanced Applications, DASFAA 2020
Country/TerritoryKorea, Republic of
CityJeju
Period9/24/209/27/20

Keywords

  • Heterogeneous CPU-GPU computing
  • Range query
  • Similarity join
  • Super-EGO

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'HEGJoin: Heterogeneous CPU-GPU Epsilon Grids for Accelerated Distance Similarity Join'. Together they form a unique fingerprint.

Cite this