基于CUDA的高维空间检索排序

周迪斌，胡 斌，张 量，黄 勇，蒋健明

（1.杭州师范大学国际服务工程学院，浙江杭州 310016；2.贝德福德大学，英国鲁顿，LU1 3JU；3.广西民族大学数学与计算机科学学院，广西南宁 530006）

基于CUDA的高维空间检索排序

周迪斌1，2，胡 斌1，张 量1，2，黄 勇3，蒋健明1

（1.杭州师范大学国际服务工程学院，浙江杭州 310016；2.贝德福德大学，英国鲁顿，LU1 3JU；3.广西民族大学数学与计算机科学学院，广西南宁 530006）

高维空间的近邻检索是多媒体信息领域的重要研究课题.文章提出一种基于CUDA的高维空间距离检索排序算法，通过并行优化空间距离计算及排序过程，充分利用GPU硬件特性和它的并行运算能力，能极大地提高高维空间的检索速度，并可获取精确的距离排序数据.实验结果表明，该文算法可达到百万级别高维数据的实时检索，极大地拓展了高维检索的应用范围.

高维数据；近邻检索；CUDA；并行计算

0 引 言

高维空间的近邻检索是多媒体信息领域的一项重要研究课题，常需要从大量数据集中查找与给定对象最相似的多个对象，也就是常说的相似性检索，在视频、音频、图像、文本等含丰富特征信息领域中的应用已经变得越来越重要.随着互联网技术的发展和多媒体技术更深入广泛的运用，对高维空间检索技术提出了更高的性能要求，如算法的时间、空间复杂度，算法准确性、鲁棒性，甚至是实时性.例如基于以图搜图技术的互联网图像检索，就是一个典型的实时性要求很高的运用领域，需要从互联网上的……