2018年秋季学期视觉计算实验室第10周论文研读预告

论文研读时间: 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. 向大家介绍异构计算的思想和优点,可以在以后的学习和工作中使用。

论文简介
  1. 内容简介
    相似搜索,又称k近邻搜索,是数据挖掘应用程序的关键部分。它涉及到搜索每个查询的前k个搜索结果。由于数据量巨大,在计算速度和并发性能上对计算机有着很高的要求。随着图形处理单元(GPU)在数据挖掘任务中的应用越来越普遍,本文提出了TH-heap算法,使用GPU进行距离计算,提出使用阈值对要排序的数据量进行压缩,提出minmax堆提高排序效率,能在同时集成了GPU和CPU的机器上运行,实现了异构计算,大大提升效率。
  2. 主要贡献
    本文提出了一个新的精确kNN算法,比目前最先进的并行部分排序的kNN算法更快。做出的主要贡献包括:
    • 基于快速采样的剪枝方法压缩距离矩阵
    • 使用查询批处理并行实现部分minmax堆排序
  3. 内容详解
    精确相似搜索可以分解为两种基本操作:数据点与查询点之间的距离计算,然后对结果进行排序以找到最小的距离(即,与查询点最相似的点)。距离计算是一项高度可并行化的任务,非常适合GPU。在该算法中,距离计算发生了两次:第一次是抽样的小样本上,用于确定k近邻的阈值。第二次是在整个数据集上。排序也是一个需要考虑的大成本,对此本文提出了基于阈值的修剪来降低排序涉及的数据量;然后提出使用minmax堆进行排序。
  4. 算法步骤
    本文提出的TH-heap算法有四个主要阶段:采样、距离计算、压缩和排序。(假设我们要得到离查询点最近的k个点)
    1. 采样
      先根据k值和数据集的大小确定一个采样集的大小,文中给出了合适的采样集大小的确定方法。然后使用GPU并行计算出采样集中的每一点与查询点间的距离,从中找到第k小的距离,作为阈值。
    2. 距离计算
      使用GPU并行计算出数据集中的每一个点与查询点的距离。
    3. 压缩
      数据集中得到的距离比阈值大,就舍弃,得到缩小后的数据集。
    4. 排序
      使用min-max堆,维护一个有k个元素的堆。当缩小后的数据集中的所有元素插入完成后,就得到了最小的k个元素。
123