An empirical evaluation of exact set similarity join techniques using GPUs. (March 2020) - Bellas, Christos; Gounaris, Anastasios
Abstract: Exact set similarity join is a notoriously expensive operation, for which several solutions have been proposed. Recently, there have been studies that present a comparative analysis using MapReduce or a non-parallel setting. Our contribution is that we complement these works through conducting a thorough evaluation of the state-of-the-art GPU-enabled techniques. These techniques are highly diverse in their key features and our experiments manage to reveal the key strengths of each one. As we explain, in real-life applications there is no dominant solution. Depending on specific dataset and query characteristics, each solution, even not using the GPU at all, has its own sweet spot. All our work is repeatable and extensible. Highlights: A thorough evaluation showing the sweet spot of each different technique for exact set similarity joins using a GPU. In large threshold values the sequential CPU techniques are competitive. In lower threshold values, employing parallel GPU techniques seems beneficial. Overall, GPU techniques may perform worse due to the imposed quadratic space overhead. A CPU-GPU co-process scheme performs better in some cases due to efficient workload balance.