GPU-Accelerated Similarity Self-Join for Multi-Dimensional Data
GPU-Accelerated Similarity Self-Join for Multi-Dimensional Data
复制标题
DOI：
10.1145/3329785.3329920
复制
发表时间：
2018-09
期刊：
影响因子：
--
通讯作者：
M. Gowanlock;Ben Karsin
中科院分区：
文献类型：
--
作者：
M. Gowanlock;Ben Karsin
相似性自连接查找数据集中彼此在搜索距离 ε 内的所有对象。因此，自连接是许多算法的构建块。在高维度中，索引结构在修剪搜索方面变得越来越无效，使得自连接难以高效计算。我们提出了一种针对高维数据的 GPU 加速自连接算法。 GPU 提供的大规模并行性和高聚合内存带宽使该架构非常适合数据密集型工作负载。我们利用基于网格的 GPU 定制索引来执行范围查询，并提出以下优化：（i）通过利用索引的属性在候选集过滤和索引搜索开销之间进行权衡； (ii)根据各维度的方差对数据进行重新排序，以提高指标的过滤能力； (iii)用于减少昂贵的距离计算次数的修剪方法。我们的算法通常优于并行 CPU 最先进的方法。
The similarity self-join finds all objects in a dataset that are within a search distance, ∈, of each other. As such, the self-join is a building block of many algorithms. In high dimensions, indexing structures become increasingly ineffective at pruning the search, making the self-join challenging to compute efficiently. We advance a GPU-accelerated self-join algorithm targeted towards high dimensional data. The massive parallelism afforded by the GPU and high aggregate memory bandwidth makes the architecture well-suited for data-intensive workloads. We leverage a grid-based GPU-tailored index to perform range queries, and propose the following optimizations: (i) a trade-off between candidate set filtering and index search overhead by exploiting properties of the index; (ii) reordering the data based on variance in each dimension to improve the filtering power of the index; and (iii) a pruning method for reducing the number of expensive distance calculations. Our algorithm generally outperforms a parallel CPU state-of-the-art approach.