论文研读时间： 2018年11月9日9点30分
论文研读地点： 四川大学望江校区基础教学楼B座318（视觉计算实验室）
论文分享者： 申航，周弋航
分享内容：Accelerating Exact Similarity Search on CPU-GPU Systems
分享来源：2015 IEEE International Conference on Data Mining
分享理由:
1. 本文结构明确，背景阐述充足，读来清晰易懂。
2. 提出算法的思路比如：让GPU做距离计算、取样得到数据集分布、使用阈值减少计算量、维护堆得到前k个值、查询批处理等想法在以后设计算法中也能使用，提高效率、降低计算量。
3. 向大家介绍异构计算的思想和优点，可以在以后的学习和工作中使用。
论文简介
- 内容简介
相似搜索，又称k近邻搜索，是数据挖掘应用程序的关键部分。它涉及到搜索每个查询的前k个搜索结果。由于数据量巨大，在计算速度和并发性能上对计算机有着很高的要求。随着图形处理单元(GPU)在数据挖掘任务中的应用越来越普遍，本文提出了TH-heap算法，使用GPU进行距离计算，提出使用阈值对要排序的数据量进行压缩，提出minmax堆提高排序效率，能在同时集成了GPU和CPU的机器上运行，实现了异构计算，大大提升效率。 - 主要贡献
本文提出了一个新的精确kNN算法，比目前最先进的并行部分排序的kNN算法更快。做出的主要贡献包括：- 基于快速采样的剪枝方法压缩距离矩阵
- 使用查询批处理并行实现部分minmax堆排序
- 内容详解
精确相似搜索可以分解为两种基本操作:数据点与查询点之间的距离计算，然后对结果进行排序以找到最小的距离(即，与查询点最相似的点)。距离计算是一项高度可并行化的任务，非常适合GPU。在该算法中，距离计算发生了两次:第一次是抽样的小样本上，用于确定k近邻的阈值。第二次是在整个数据集上。排序也是一个需要考虑的大成本，对此本文提出了基于阈值的修剪来降低排序涉及的数据量；然后提出使用minmax堆进行排序。 - 算法步骤
本文提出的TH-heap算法有四个主要阶段:采样、距离计算、压缩和排序。（假设我们要得到离查询点最近的k个点）- 采样
先根据k值和数据集的大小确定一个采样集的大小，文中给出了合适的采样集大小的确定方法。然后使用GPU并行计算出采样集中的每一点与查询点间的距离，从中找到第k小的距离，作为阈值。 - 距离计算
使用GPU并行计算出数据集中的每一个点与查询点的距离。 - 压缩
数据集中得到的距离比阈值大，就舍弃，得到缩小后的数据集。 - 排序
使用min-max堆，维护一个有k个元素的堆。当缩小后的数据集中的所有元素插入完成后，就得到了最小的k个元素。
- 采样