基于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 引 言

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

实现近邻查询最简单的方法是顺序扫描，但当数据量较大时，全局需要耗费大量的磁盘开销和运算时间，缺乏可行性.为了提高查询效率，许多学者提出了各种基于索引结构或者hash算法以便提高检索速度.算法效率虽然提高很多，但是这些算法普遍存在准确性不足的问题，一般都是近似解，同时算法各种索引结构可能比较复杂，很多算法具有很强的适应性，依赖于特定数据集，很难做到完全通用.

另一方面，GPU硬件技术发展迅速，尤其是基于GPU的通用计算平台CUDA（Compute Unified Device Architecture）推出后，更加快了基于单机平台的并行算法研究与设计及其在各个领域的应用.GPU内部包含数百个微处理单元，具有很强的并行运算能力，这为各种新的并行算法结构研究提供了有力的支撑.为此，该文提出了一种基于CUDA的高维空间检索方法，能充分挖掘GPU硬件并行特性.通过并行实现高索引过程中的距离计算及排序，算法能极大地提高检索效率，同时，由于算法结构是扫描式的，算法可轻易取得精确排序结果，具有很好的鲁棒性.实验表明，该文算法完全可以满足百万级别甚至千万级别的高维检索的实时性和精确性要求.

1 研究背景

高维索引的研究始于20世纪70年代，涉及CAD、GIS，数据库管理和模式识别等应用，到20世纪90年代，随着互联网技术和多媒体技术等领域快速进展，进一步增加了对高维数据检索的需求，如基于互联网的图像检索，音频检索.此时，数据规模进一步增加，从几十万到几十亿，大部分数据以高维向量的形式存在，高达几百维或上千维.如何提高高维向量空间的检索效率成为很多学者关注的研究热点.

对于高维数据，由于其自身的无序性、复杂性等特点，使得传统关系型数据库中的索引结构无法适用.在过去的几十年中，大量的高维数据索引结构被相继提出，其中树形检索结构运用最多，包括以空间划分为基础算法，如四叉树［1］、k－d树［2］、k－d－b树［3］等，和以数据划分为基础的算法，如R树法及其变种［4－6］、TV树法［7］、X－Tree法［8］等.此类算法能精确返回计算结果，但当数据维数较高时，它们都很难表现出令人满意的查询性能，即面临所谓的维数灾难［9－10］.除了此类树形检索外，还有部分非树形索引算法，如VAFile［9］采用了量化压缩的方法来减少查询过程中的磁盘访问代价，但其近似文件仅仅是近似矢量的简单排列，其查询性能加速限制在很小的范围内，仍难以满足实际应用的需要.随后，Ferhatosmanoglu等［11］提出改进的VA＋－File方法，针对非均匀分布的数据集，能取得较好的检索性能.董国道等［12］学者又提出了一种综合的高维索引结构VA－Trie，该方法采用近似vA＿FiIc和A＿Tree中的近似思想，并借助Trie结构来组织和管理压缩后的近似矢量，以避免维度灾难.庄毅等［13］学者又提出了一种基于双重距离尺度的新型高维索引结构，能有效地缩小搜索空间，并能减少距离计算的开销，特别适合海量高维数据的查询.

近些年来，位置敏感的哈希（Locality Sensitive Hashing，LSH）算法备受国内外学术界的关注，因为它能在保证一定程度上准确性的前提下，使得时间和空间复杂度得到降低，能成功解决高维近邻数据的快速检索问题.早在1998年，Indy P和Motwani R就提出了LSH算法的理论基础［14］.随后，Indy P等又引入Basic LSH算法雏形，并成功解决了高维数据的快速检索问题引［15］.2004年，Ravichandran D［16］改进了Basic LSH算法，并成功应用于自然语言处理.2005年，Bawa M等又提出了LSH Forest算法［17］，该算法使用树形结构代替哈希表，具有自我校正参数的能力.2006年，Alexandr Andoni等将LSH算法应用于字符串匹配，能极大的提高匹配效率［18］.2007年，Josephson W和Wang Zhe［19］使用多重探测的方法改进了基于欧拉空间的LSH算法，优化了算法的时间空间效率.最近，Andoni A和Indyk P又提出一种近似最优的LSH算法［20］.

在高维检索领域，学术界已经做了大量的研究，提出了很多算法及索引结构，极大地提高算法的准确度，空间、时间效率及高维度的适应性，很多算法运算效率很高，且不需要特殊硬件支持.但这些算法也存在一些局限性，如算法设计一般比较复杂，随着数据特点不同，算法可能采用不同的策略或思路，很多方式求得近似解，非精确解，查询结果准确性易受数据聚类方法影响，还有与查询参照数据有关，还有，部分精确求解方法会导致算法效率极低，需要搜索整个查询空间，一些算法又在存储空间上有更高的要求.

新的硬件技术发展为新算法技术和理论研究提供了新的支撑，下面详细介绍该文算法.

2 算法介绍

不同于以前优化索引算法加速策略，基于CUDA的高维空间检索排序算法在某种意义上是一种暴力求解法，通过检索整个高维数据集，计算其距离并通过排序过程来实现近邻数据集检索.但与简单的扫描算法不同，该距离计算和排序过程挖掘了现有硬件的并行特性，采用基于GPU平台的CUDA框架，能有效提高算法的速率.

图1描述了算法流程，其中右边是检索过程的主要步骤，包括数据导入、距离计算、排序和数据导出.其中距离计算和排序是算法的重点，其效率与GPU性能及算法并行度息息相关，核心是如何充分利用GPU内在特性加速检索效率.下面具体分析如何最大程度挖掘GPU的流处理器硬件特性及并行特性加快运算.

图1 算法流程Fig 1 The algorithm flowchart

2.1 数据导入

基于CUDA体系架构的数据必须存贮在显存中，显存读写速度一般较内存读写的速度要快.该过程主要将计算所需的数据预先导入到显存中，便于后续的距离计算及排序.除了导入待查询的高维数据集，还需为后续距离计算及排序分配相应空间.

2.2 距离计算

依据输入的参照数据，计算各数据集与参照点的距离，计算公式采用欧拉空间公式即可.

其中a为数据集参照向量，x为高维度空间X中任意向量，n为高维空间维度.在不影响距离排序的前提下，距离公式可简化为

参照式（2），每次距离计算需处理n次减法，n次乘法和n－1次加法，整个计算过程是耗费时间最多部分，其效率决定整体效率.CUDA作为统一计算架构的体系架构，可将GPU内部众多的流处理器串联起来，联合解决数据密集的计算.同时可保证各个流处理器之间能够交换，同步及共享数据.为了使得距离计算最大程度并行化，需合理分配GPU内部各线程任务，避免写冲突.

所有待查询数据集线性存储，对于矢量数据与参照点的距离计算需多个线性协同完成，分为三部分：

1）欧拉距离计算分解，如m个线程并行参与，每个线程计算N/m个子距离分量，如第i个线程计算所有其对应分量：

其中下标t＝i＋k＊m（k＝0，1，2，3…N/m）.

2）欧拉距离分量合并，每次减半，直到合并完毕.

3）输出欧拉距离到指定位置，以便后续排序计算.

图2显示了距离的并行计算原理.假定矢量为128维，CUDA环境中每个block包含16个线程，则向量计算由16个线程（T0－T15）协作完成.各个线程按固定间隔读取相应的维度信息，计算其与相应的参照元差值，并汇总求和.如线程T0统计了a0，a16，a32，a48，a64，a80，a96，a112与相应参照点距离差平方.即：

当线程统计各自距离分量后，经同步达到第二过程，此时，共有16个分量Di（i＝0－15）.连续两两合并，降为8分量，4分量，2分量，最后合并为一个值.过程如下：

原始数据：D0－D15

第一次合并：输出D0－D7，间隔为8，参与线程T0－T7

第二次合并：输出D0－D3，间隔为4，参与线程T0－T3

第三次合并：输出D0－D1，间隔为2，参与线程T0－T1

第四次合并：输出D0，间隔为1，参与线程T0

此时D＝D0，输出D0即可.

从并行性能上分析，第一部分是计算欧拉子距离，所有线程均参与，任务平均分配；而第二部分是欧拉子距离分量合并，每次参与线程减半.第三部分输出到指定位置，只有特定线程可写，以避免读写冲突.

图2 距离并行计算Fig 2 Parallel distance computation

2.3 距离排序

依据距离计算的结果，需要进一步对距离进行排序以确定最近邻关系.在排序算法方面，基数排序是目前最快的算法，算法复杂度最低为O（n）.传统的基数排序算法仅适合于整数，通过对于浮点数适当的变换，基数排序可适用于浮点数.

目前，Satish N［21］等已经在CUDA平台实现了基数排序算法，该文算法直接采用其算法框架实现距离排序，具体可以参照论文.该算法实现效率极高，依据GPU性能，一般可以达到每秒排序上亿数据，至少高出基于CPU的基数排序算法1个数量级以上.

2.4 数据导出

排序后数据及其索引存储在显存中，不能直接读取，需导出到内存.一般导出排序好的索引值即可.

针对特定的数据集检索，数据导入过程仅需在检索过程时初始化一次即可.应用系统仅需输入所需检索的数据，检索系统通过距离计算、排序，最后输出检索结果.

3 实验与性能分析

实验测试平台选择了系统采用64位Windows 7pro平台，配有Nvidia Tesla GPU C1060的GPU，含2G显存.表1显示了算法各部分时间统计结果，其中，矢量数据从100万—500万，数据维度则选择了128维（2Byte）和256维（1Byte）随机数.

结果表明，随着数据规模增加，距离计算、排序、数据导出和总时间线性增加.对于500万规模的高维数据查询，该文算法基本可以达到实时需求，一般可控制在60～500ms之间，且能获得准确排序.如果应用系统无需获取所有的排序结果，则可以减少数据导出量，数据导出时间能相应减少.相对于传统基于内存的线性查找算法，时间一般在数秒或数十秒之间.

同时，性能分析显示距离计算时间占检索时间比重最大，这主要是高维距离计算时间复杂度与数据维度相关，维度越高，参与计算的特征分量就越多，时间耗费越多，而排序时间和数据导出时间，只与参与排序的数据量有关，与数据维度有关.图3性能分析验证了该结果：（1）部分显示距离计算，效率与数据维度相关，随数据维度增加，计算时间成比例增加，（2）和（3）分别显示了排序时间和数据导出时间分析结果，与数据维度无关，只与总数据规模有关.

在数据存储上，需要存储特征数据及其与距离计算结果，500万128维数据，每维数据2Byte，大概需要消耗1.28G显存，远低于其它优化检索算法的存储消耗.对于更大规模的数据测试，考虑显存容量限制，系统暂不支持.

表1 高维数据检索时间统计Tab 1 The statistice of high－dimensional data retrieval

图3 高维数据检索性能分析Fig 3 The performance analysis of high－dimensinal data retrieval

4 总结与展望

随着GPU硬件技术的发展及相应的通用计算平台软件标准的提出和深化，为各种传统算法的并行优化提供了新的基础.基此，该文提出了一种基于CUDA的高维空间距离检索算法，通过并行优化空间距离计算及排序过程，借助最新的图形硬件的并行运算能力，能极大提高检索速度，在单机平台上实现百万级别的高维空间实时检索以及极大推动各种相关领域的实时应用，如实时多媒体数据检索，以及数据库检索.同时，算法能实现精确检索，避免以往的优化算法存在的数据依赖性和检索结果的不稳定性.

今后的研究，进一步利用硬件特性及优化算法以提高并行效率，同时，研究有效策略减少数据维度非规则化（例如维度非2的N次幂）导致的效率下降.对于更高维的空间数据且存在大量0值的空间数据，将研究有效的数据压缩方式，提高空间利用率和检索效率.同时，在单GPU并行算法的研究基础上，进一步研究多GPU并行运算技术，以实现亿万级别的实时高效检索.

致谢：感谢图酷科技公司的胡保坤、胡静提供了部分性能测试结果.

［1］Finkel R，Bentley JL.Quad－trees：a data structure for retrieval on composite keys［J］.Acta Informatica，1974，4（1）：1－9.

［2］Bentley J L.Multidimensional binary search trees used for associative searching［J］.Communications of the ACM，1975，18（9）：509－517.

［3］Robinson J T.The K－D－B－tree：a search structure for large multidimensional dynamic indexes［C］//Proceedings of the ACM SIGMOD International Conference on Management of data.Michigan，1981：10－18.

［4］Guttman A.R－tree：a dynamic index structure for spatial searching［C］//Proceedings of the ACM SIGMOD International Conference on Management of data，Boston，1984：47－57.

［5］Beckmann N，Kriegel H P，Schneider R，etal.The R＊－tree：an efficient and robust access method for points and rectangles［J］.ACM SIGMOD Record，1990，19（2）：322－331.

［6］Sellis T K，Roussopoulos N，Faloutsos C.The R＋－tree：a dynamic index for multidimensional objects［C］//Proceedings of the 13th VLDB Conference，England.Morgan Kaufmann Publishers，California，1987：507－518.

［7］Lin K I，Jagadish H，Faloutsos C.The TV－tree：an index structure for high－dimensional data［J］.The International Journal on Very Large Data Bases，1994，3（4）：517－542

［8］Berchtold S，Keim DA，Kriegel H P.The X－tree：an index structure for high－dimensional data［C］//Proceedings of the 22nd International Conference on Very Large Data Bases，Munich，1996：28－39.

［9］Weber R，Schek H J，Blott S.A quantitative analysis and performance study for similarity－search methods in high dimensional spaces［C］//Proceedings of the 24th International Conference on Very Large Data Bases，New York，1998：194－205.

［10］Berchtold S，Kriegel C，Hriegel H.The pyramid－tree：breaking the curse of dimensionality［C］//Proceedings of ACM Sigmod Conference，Washington，1998：142－153.

［11］Ferhatosmanoglu H，Tuncel E，Agrawal D.Vector approximation based indexing for non－uniform high dimensional data sets［C］//Proceedings of the 9th International Conference on Information and Knowledge Management，New York，2000：202－209.

［12］董道国，刘振中，薛向阳.VA－Trie：一种用于近似k近邻查询的高维索引结构［J］.计算机研究与发展，2005，42（12）：2213－2218.

［13］庄毅，翁建广，庄越挺，等.一种基于双重距离尺度的高维索引结构［J］.浙江大学学报：工学版，2007，41（3）：380－385.

［14］Indyk P，Motwani R.Approximate nearest neighbors：towards removing the curse of dimensionality［C］//Proceedings of the thirtieth annual ACM symposium on theory of computing，Dallas：1998：604－613.

［15］Indyk P，Datar M，Immorlica N.Locality－sensitive hashing scheme based on p－Stable［C］//Proceedings of the tmentieth annual Symposium on Computational Geometry.New York，2004：253－262.

［16］Ravichandran D，Pantel P，Hovy E.Randomized algorithms and NLP：using locality sensitive hash function for high speed noun clustering［C］//Proceedings of the 43rd Annual Meeting on Association for Computational Linguistic，Michigan，2005：622－629.

［17］Bawa M，Condie T，Ganesan P.LSH forest：self－tuning indexes for similarity search［C］//Proceedings of the 14th International Conference on World Wide Web，Chiba，2005：651－660.

［18］Andoni A，Indyk P.Efficient algorithms for substring near neighbor problem［C］//Proceedings of the Seventeenth Annual ACM－SIAM Symposium on Discrete Algorithms，Miami，2006：1203－1212.

［19］Li Qin，Josephson W，Wang Zhe，etal.Multi probe LSH：efficient indexing for high dimensional similarity search［C］//Proceedings of the 33rd International Conference on Very Large Data Bases.Vienna，2007：950－961.

［20］Andoni A，Indyk P.Near－optimal hashing algorithms for approximate nearest neighbor in high dimensions［C］//Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science，Berkeley，2006：459－468.

［21］Satish N，Harris M，Garland M.Designing efficient sorting algorithms for manycore GPUs［C］//Proceedings of IEEE International Symposium on Parallel ＆Distributed Processing Symposium.Rome，2009：1－10.

High－Dimensional Space Retrieval Sorting Based on CUDA

ZHOU Di－bin1，2，HU Bin1，Zhang Liang1，2，HUANG Yong3，JIANG Jian－ming1

（1.College of International Service Engineering，Hangzhou Normal University，Hangzhou 310016，China；
2.University of Bedfordshire，Luton LU1 3JU，UK；
3.College of Mathematics and Computer Science，Guangxi University for Nationalities，Nanning 530006，China）

Near neighbor searching in high－dimensional space is one of important research fields.This paper presented a high－dimensional space distance retrieval sorting algonithm based on CUDA.By optimizing distance calculation and parallel sort，extremely utilizing the features of GPU and its ability of parallel computation，the algorithm can not only effectively improve the searching speed，but also can acquire exact distance sequence data.The experiment results show that the algorithm can support real－time retrieval for millions of high－dimensional data，which can greatly extend the application of high－dimensional retrieval.

high－dimensional data，near neighbor searching，CUDA，parallel computation

TP311.3

A

1674－232X（2011）05－0459－07

10.3969/j.issn.1674－232X.2011.05.014

2010－12－19

中小企业创新基金项目（10C26213304161）；浙江省教育厅科研基金项目（Y200805962）.

周迪斌（1978—），男，江西安义人，讲师，博士，贝德福德大学在职博士后，主要从事科学计算可视化和并行计算研究.E－mail：dibin.z＠163.com