NDLI: Fast Equi-Join Algorithms on GPUs: Design and Implementation

Please wait, while we are loading the content...

Managing Sensor Data Streams: Lessons Learned from the WeBike Project

Measuring Fairness in Ranked Outputs

SGVCut: A Vertex-Cut Partitioning Tool for Random Walks-based Computations over Social Network graphs

Incremental Discovery of Inclusion Dependencies

How the Passengers Flow in Complex Metro Networks?

VISOR: Visualizing Summaries of Ordered Data

Generating What-If Scenarios for Time Series Data

DualDB: An Efficient LSM-based Publish/Subscribe Storage System

Skluma: A Statistical Learning Pipeline for Taming Unkempt Data Repositories

Computing Influence of a Product through Uncertain Reverse Skyline

DistriPlan: An Optimized Join Execution Framework for Geo-Distributed Scientific Data

DataSynthesizer: Privacy-Preserving Synthetic Datasets

FlatFIT: Accelerated Incremental Sliding-Window Aggregation For Real-Time Analytics

Fides: Towards a Platform for Responsible Data Science

A Benchmark for Betweenness Centrality Approximation Algorithms on Large Graphs

Challenges of Differentially Private Release of Data Under an Open-world Assumption

Incremental Temporal Pattern Mining Using Efficient Batch-Free Stream Clustering

Mining Persistent and Discriminative Communities in Graph Ensembles

Dot-Product Join: Scalable In-Database Linear Algebra for Big Model Analytics

High-Definition Digital Elevation Model System Vision Paper

On-line Versioned Schema Inference for Large Semantic Web Data Sources

Discovering Partial Periodic Itemsets in Temporal Databases

Bi-Level Online Aggregation on Raw Data

Detecting Global Hyperparaboloid Correlated Clusters Based on Hough Transform

Tiling Strategies for Distributed Point Cloud Databases

Edge Labeling Schemes for Graph Data

Computing Isochrones in Multimodal Spatial Networks using Tile Regions

Class-based Conditional MaxRS Query in Spatial Data Streams

Location and Processing Aware Datacube Caching

Active Learning with Density-Initialized Decision Tree for Record Matching

MELT: Mapreduce-based Efficient Large-scale Trajectory Anonymization

BLOCK: Efficient Execution of Spatial Range Queries in Main-Memory

PLI: Augmenting Live Databases with Custom Clustered Indexes

Multi-Hypothesis CSV Parsing

Improving Statistical Similarity Based Data Reduction for Non-Stationary Data

Fast Equi-Join Algorithms on GPUs: Design and Implementation

Dynamic Group Trip Planning Queries in Spatial Databases

Query Suggestion to allow Intuitive Interactive Search in Multidimensional Time Series

SHRec: Scalable Holistic Recommendation

A Unified Correlation-based Approach to Sampling Over Joins

Probabilistic k-Nearest Neighbor Monitoring of Moving Gaussians

Fast Equi-Join Algorithms on GPUs: Design and Implementation

Content Provider	ACM Digital Library
Author	Tu, Yi-Cheng Rui, Ran
Abstract	Processing relational joins on modern GPUs has attracted much attention in the past few years. With the rapid development on the hardware and software environment in the GPU world, the existing GPU join algorithms designed for earlier architecture cannot make the most out of latest GPU products. In this paper, we report new design and implementation of join algorithms with high performance under today's GPGPU environment. This is a key component of our scientific database engine named G-SDMS. In particular, we overhaul the popular radix hash join and redesign sort-merge join algorithms on GPUs by applying a series of novel techniques to utilize the hardware capacity of latest Nvidia GPU architecture and new features of the CUDA programming framework. Our algorithms take advantage of revised hardware arrangement, larger register file and shared memory, native atomic operation, dynamic parallelism, and CUDA Streams. Experiments show that our new hash join algorithm is 2.0 to 14.6 times as efficient as existing GPU implementation, while the new sort-merge join achieves a speedup of 4.0X to 4.9X. Compared to the best CPU sort-merge join and hash join known to date, our optimized code achieves up to 10.5X and 5.5X speedup. Moreover, we extend our design to scenarios where large data tables cannot fit in the GPU memory.
Starting Page	1
Ending Page	12
Page Count	12
File Format	PDF
ISBN	9781450352826
DOI	10.1145/3085504.3085521
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2017-06-27
Publisher Place	New York
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

GBFSJ: Bloom Filter Star Join algorithms on GPUs

Implementation of parallel collection equi-join using mpi.

An analysis of two-way equi-join algorithms under MapReduce

Performance Analysis of Join Algorithms on GPUs

Parallel Fast Möbius (Reed-Muller) Transform and its Implementation with CUDA on GPUs

Fragment and replicate algorithms for non-equi-join evaluation on Smart Disks

Join algorithms on GPUs: A revisit after seven years

Memory footprint matters: efficient equi-join algorithms for main memory data processing

Efficient Algorithm for Overlap-Join

Fast Equi-Join Algorithms on GPUs: Design and Implementation

Similar Documents

GBFSJ: Bloom Filter Star Join algorithms on GPUs

Implementation of parallel collection equi-join using mpi.

An analysis of two-way equi-join algorithms under MapReduce

Performance Analysis of Join Algorithms on GPUs

Parallel Fast Möbius (Reed-Muller) Transform and its Implementation with CUDA on GPUs

Fragment and replicate algorithms for non-equi-join evaluation on Smart Disks

Join algorithms on GPUs: A revisit after seven years

Memory footprint matters: efficient equi-join algorithms for main memory data processing

Efficient Algorithm for Overlap-Join

Fast Equi-Join Algorithms on GPUs: Design and Implementation