周迪斌，胡 斌，張 量，黃 勇，蔣健明

（1.杭州師范大學國際服務工程學院，浙江杭州 310016；2.貝德福德大學，英國魯頓，LU1 3JU；3.廣西民族大學數(shù)學與計算機科學學院，廣西南寧 530006）

基于CUDA的高維空間檢索排序

周迪斌1，2，胡 斌1，張 量1，2，黃 勇3，蔣健明1

（1.杭州師范大學國際服務工程學院，浙江杭州 310016；2.貝德福德大學，英國魯頓，LU1 3JU；3.廣西民族大學數(shù)學與計算機科學學院，廣西南寧 530006）

高維空間的近鄰檢索是多媒體信息領域的重要研究課題.文章提出一種基于CUDA的高維空間距離檢索排序算法，通過并行優(yōu)化空間距離計算及排序過程，充分利用GPU硬件特性和它的并行運算能力，能極大地提高高維空間的檢索速度，并可獲取精確的距離排序數(shù)據(jù).實驗結(jié)果表明，該文算法可達到百萬級別高維數(shù)據(jù)的實時檢索，極大地拓展了高維檢索的應用范圍.

高維數(shù)據(jù)；近鄰檢索；CUDA；并行計算

0 引 言

高維空間的近鄰檢索是多媒體信息領域的一項重要研究課題，常需要從大量數(shù)據(jù)集中查找與給定對象最相似的多個對象，也就是常說的相似性檢索，在視頻、音頻、圖像、文本等含豐富特征信息領域中的應用已經(jīng)變得越來越重要.隨著互聯(lián)網(wǎng)技術的發(fā)展和多媒體技術更深入廣泛的運用，對高維空間檢索技術提出了更高的性能要求，如算法的時間、空間復雜度，算法準確性、魯棒性，甚至是實時性.例如基于以圖搜圖技術的互聯(lián)網(wǎng)圖像檢索，就是一個典型的實時性要求很高的運用領域，需要從互聯(lián)網(wǎng)上的幾百萬到數(shù)十億張圖片中迅速查找最相似圖片，并反饋給用戶.

實現(xiàn)近鄰查詢最簡單的方法是順序掃描，但當數(shù)據(jù)量較大時，全局需要耗費大量的磁盤開銷和運算時間，缺乏可行性.為了提高查詢效率，許多學者提出了各種基于索引結(jié)構(gòu)或者hash算法以便提高檢索速度.算法效率雖然提高很多，但是這些算法普遍存在準確性不足的問題，一般都是近似解，同時算法各種索引結(jié)構(gòu)可能比較復雜，很多算法具有很強的適應性，依賴于特定數(shù)據(jù)集，很難做到完全通用.

另一方面，GPU硬件技術發(fā)展迅速，尤其是基于GPU的通用計算平臺CUDA（Compute Unified Device Architecture）推出后，更加快了基于單機平臺的并行算法研究與設計及其在各個領域的應用.GPU內(nèi)部包含數(shù)百個微處理單元，具有很強的并行運算能力，這為各種新的并行算法結(jié)構(gòu)研究提供了有力的支撐.為此，該文提出了一種基于CUDA的高維空間檢索方法，能充分挖掘GPU硬件并行特性.通過并行實現(xiàn)高索引過程中的距離計算及排序，算法能極大地提高檢索效率，同時，由于算法結(jié)構(gòu)是掃描式的，算法可輕易取得精確排序結(jié)果，具有很好的魯棒性.實驗表明，該文算法完全可以滿足百萬級別甚至千萬級別的高維檢索的實時性和精確性要求.

1 研究背景

高維索引的研究始于20世紀70年代，涉及CAD、GIS，數(shù)據(jù)庫管理和模式識別等應用，到20世紀90年代，隨著互聯(lián)網(wǎng)技術和多媒體技術等領域快速進展，進一步增加了對高維數(shù)據(jù)檢索的需求，如基于互聯(lián)網(wǎng)的圖像檢索，音頻檢索.此時，數(shù)據(jù)規(guī)模進一步增加，從幾十萬到幾十億，大部分數(shù)據(jù)以高維向量的形式存在，高達幾百維或上千維.如何提高高維向量空間的檢索效率成為很多學者關注的研究熱點.

對于高維數(shù)據(jù)，由于其自身的無序性、復雜性等特點，使得傳統(tǒng)關系型數(shù)據(jù)庫中的索引結(jié)構(gòu)無法適用.在過去的幾十年中，大量的高維數(shù)據(jù)索引結(jié)構(gòu)被相繼提出，其中樹形檢索結(jié)構(gòu)運用最多，包括以空間劃分為基礎算法，如四叉樹［1］、k－d樹［2］、k－d－b樹［3］等，和以數(shù)據(jù)劃分為基礎的算法，如R樹法及其變種［4－6］、TV樹法［7］、X－Tree法［8］等.此類算法能精確返回計算結(jié)果，但當數(shù)據(jù)維數(shù)較高時，它們都很難表現(xiàn)出令人滿意的查詢性能，即面臨所謂的維數(shù)災難［9－10］.除了此類樹形檢索外，還有部分非樹形索引算法，如VAFile［9］采用了量化壓縮的方法來減少查詢過程中的磁盤訪問代價，但其近似文件僅僅是近似矢量的簡單排列，其查詢性能加速限制在很小的范圍內(nèi)，仍難以滿足實際應用的需要.隨后，F(xiàn)erhatosmanoglu等［11］提出改進的VA＋－File方法，針對非均勻分布的數(shù)據(jù)集，能取得較好的檢索性能.董國道等［12］學者又提出了一種綜合的高維索引結(jié)構(gòu)VA－Trie，該方法采用近似vA＿FiIc和A＿Tree中的近似思想，并借助Trie結(jié)構(gòu)來組織和管理壓縮后的近似矢量，以避免維度災難.莊毅等［13］學者又提出了一種基于雙重距離尺度的新型高維索引結(jié)構(gòu)，能有效地縮小搜索空間，并能減少距離計算的開銷，特別適合海量高維數(shù)據(jù)的查詢.

近些年來，位置敏感的哈希（Locality Sensitive Hashing，LSH）算法備受國內(nèi)外學術界的關注，因為它能在保證一定程度上準確性的前提下，使得時間和空間復雜度得到降低，能成功解決高維近鄰數(shù)據(jù)的快速檢索問題.早在1998年，Indy P和Motwani R就提出了LSH算法的理論基礎［14］.隨后，Indy P等又引入Basic LSH算法雛形，并成功解決了高維數(shù)據(jù)的快速檢索問題引［15］.2004年，Ravichandran D［16］改進了Basic LSH算法，并成功應用于自然語言處理.2005年，Bawa M等又提出了LSH Forest算法［17］，該算法使用樹形結(jié)構(gòu)代替哈希表，具有自我校正參數(shù)的能力.2006年，Alexandr Andoni等將LSH算法應用于字符串匹配，能極大的提高匹配效率［18］.2007年，Josephson W和Wang Zhe［19］使用多重探測的方法改進了基于歐拉空間的LSH算法，優(yōu)化了算法的時間空間效率.最近，Andoni A和Indyk P又提出一種近似最優(yōu)的LSH算法［20］.

在高維檢索領域，學術界已經(jīng)做了大量的研究，提出了很多算法及索引結(jié)構(gòu)，極大地提高算法的準確度，空間、時間效率及高維度的適應性，很多算法運算效率很高，且不需要特殊硬件支持.但這些算法也存在一些局限性，如算法設計一般比較復雜，隨著數(shù)據(jù)特點不同，算法可能采用不同的策略或思路，很多方式求得近似解，非精確解，查詢結(jié)果準確性易受數(shù)據(jù)聚類方法影響，還有與查詢參照數(shù)據(jù)有關，還有，部分精確求解方法會導致算法效率極低，需要搜索整個查詢空間，一些算法又在存儲空間上有更高的要求.

新的硬件技術發(fā)展為新算法技術和理論研究提供了新的支撐，下面詳細介紹該文算法.

2 算法介紹

不同于以前優(yōu)化索引算法加速策略，基于CUDA的高維空間檢索排序算法在某種意義上是一種暴力求解法，通過檢索整個高維數(shù)據(jù)集，計算其距離并通過排序過程來實現(xiàn)近鄰數(shù)據(jù)集檢索.但與簡單的掃描算法不同，該距離計算和排序過程挖掘了現(xiàn)有硬件的并行特性，采用基于GPU平臺的CUDA框架，能有效提高算法的速率.

圖1描述了算法流程，其中右邊是檢索過程的主要步驟，包括數(shù)據(jù)導入、距離計算、排序和數(shù)據(jù)導出.其中距離計算和排序是算法的重點，其效率與GPU性能及算法并行度息息相關，核心是如何充分利用GPU內(nèi)在特性加速檢索效率.下面具體分析如何最大程度挖掘GPU的流處理器硬件特性及并行特性加快運算.

圖1 算法流程Fig 1 The algorithm flowchart

2.1 數(shù)據(jù)導入

基于CUDA體系架構(gòu)的數(shù)據(jù)必須存貯在顯存中，顯存讀寫速度一般較內(nèi)存讀寫的速度要快.該過程主要將計算所需的數(shù)據(jù)預先導入到顯存中，便于后續(xù)的距離計算及排序.除了導入待查詢的高維數(shù)據(jù)集，還需為后續(xù)距離計算及排序分配相應空間.

2.2 距離計算

依據(jù)輸入的參照數(shù)據(jù)，計算各數(shù)據(jù)集與參照點的距離，計算公式采用歐拉空間公式即可.

其中a為數(shù)據(jù)集參照向量，x為高維度空間X中任意向量，n為高維空間維度.在不影響距離排序的前提下，距離公式可簡化為

參照式（2），每次距離計算需處理n次減法，n次乘法和n－1次加法，整個計算過程是耗費時間最多部分，其效率決定整體效率.CUDA作為統(tǒng)一計算架構(gòu)的體系架構(gòu)，可將GPU內(nèi)部眾多的流處理器串聯(lián)起來，聯(lián)合解決數(shù)據(jù)密集的計算.同時可保證各個流處理器之間能夠交換，同步及共享數(shù)據(jù).為了使得距離計算最大程度并行化，需合理分配GPU內(nèi)部各線程任務，避免寫沖突.

所有待查詢數(shù)據(jù)集線性存儲，對于矢量數(shù)據(jù)與參照點的距離計算需多個線性協(xié)同完成，分為三部分：

1）歐拉距離計算分解，如m個線程并行參與，每個線程計算N/m個子距離分量，如第i個線程計算所有其對應分量：

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

2）歐拉距離分量合并，每次減半，直到合并完畢.

3）輸出歐拉距離到指定位置，以便后續(xù)排序計算.

圖2顯示了距離的并行計算原理.假定矢量為128維，CUDA環(huán)境中每個block包含16個線程，則向量計算由16個線程（T0－T15）協(xié)作完成.各個線程按固定間隔讀取相應的維度信息，計算其與相應的參照元差值，并匯總求和.如線程T0統(tǒng)計了a0，a16，a32，a48，a64，a80，a96，a112與相應參照點距離差平方.即：

當線程統(tǒng)計各自距離分量后，經(jīng)同步達到第二過程，此時，共有16個分量Di（i＝0－15）.連續(xù)兩兩合并，降為8分量，4分量，2分量，最后合并為一個值.過程如下：

原始數(shù)據(jù)：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 距離排序

依據(jù)距離計算的結(jié)果，需要進一步對距離進行排序以確定最近鄰關系.在排序算法方面，基數(shù)排序是目前最快的算法，算法復雜度最低為O（n）.傳統(tǒng)的基數(shù)排序算法僅適合于整數(shù)，通過對于浮點數(shù)適當?shù)淖儞Q，基數(shù)排序可適用于浮點數(shù).

目前，Satish N［21］等已經(jīng)在CUDA平臺實現(xiàn)了基數(shù)排序算法，該文算法直接采用其算法框架實現(xiàn)距離排序，具體可以參照論文.該算法實現(xiàn)效率極高，依據(jù)GPU性能，一般可以達到每秒排序上億數(shù)據(jù)，至少高出基于CPU的基數(shù)排序算法1個數(shù)量級以上.

2.4 數(shù)據(jù)導出

排序后數(shù)據(jù)及其索引存儲在顯存中，不能直接讀取，需導出到內(nèi)存.一般導出排序好的索引值即可.

針對特定的數(shù)據(jù)集檢索，數(shù)據(jù)導入過程僅需在檢索過程時初始化一次即可.應用系統(tǒng)僅需輸入所需檢索的數(shù)據(jù)，檢索系統(tǒng)通過距離計算、排序，最后輸出檢索結(jié)果.

3 實驗與性能分析

實驗測試平臺選擇了系統(tǒng)采用64位Windows 7pro平臺，配有Nvidia Tesla GPU C1060的GPU，含2G顯存.表1顯示了算法各部分時間統(tǒng)計結(jié)果，其中，矢量數(shù)據(jù)從100萬—500萬，數(shù)據(jù)維度則選擇了128維（2Byte）和256維（1Byte）隨機數(shù).

結(jié)果表明，隨著數(shù)據(jù)規(guī)模增加，距離計算、排序、數(shù)據(jù)導出和總時間線性增加.對于500萬規(guī)模的高維數(shù)據(jù)查詢，該文算法基本可以達到實時需求，一般可控制在60～500ms之間，且能獲得準確排序.如果應用系統(tǒng)無需獲取所有的排序結(jié)果，則可以減少數(shù)據(jù)導出量，數(shù)據(jù)導出時間能相應減少.相對于傳統(tǒng)基于內(nèi)存的線性查找算法，時間一般在數(shù)秒或數(shù)十秒之間.

同時，性能分析顯示距離計算時間占檢索時間比重最大，這主要是高維距離計算時間復雜度與數(shù)據(jù)維度相關，維度越高，參與計算的特征分量就越多，時間耗費越多，而排序時間和數(shù)據(jù)導出時間，只與參與排序的數(shù)據(jù)量有關，與數(shù)據(jù)維度有關.圖3性能分析驗證了該結(jié)果：（1）部分顯示距離計算，效率與數(shù)據(jù)維度相關，隨數(shù)據(jù)維度增加，計算時間成比例增加，（2）和（3）分別顯示了排序時間和數(shù)據(jù)導出時間分析結(jié)果，與數(shù)據(jù)維度無關，只與總數(shù)據(jù)規(guī)模有關.

在數(shù)據(jù)存儲上，需要存儲特征數(shù)據(jù)及其與距離計算結(jié)果，500萬128維數(shù)據(jù)，每維數(shù)據(jù)2Byte，大概需要消耗1.28G顯存，遠低于其它優(yōu)化檢索算法的存儲消耗.對于更大規(guī)模的數(shù)據(jù)測試，考慮顯存容量限制，系統(tǒng)暫不支持.

表1 高維數(shù)據(jù)檢索時間統(tǒng)計Tab 1 The statistice of high－dimensional data retrieval

圖3 高維數(shù)據(jù)檢索性能分析Fig 3 The performance analysis of high－dimensinal data retrieval

4 總結(jié)與展望

隨著GPU硬件技術的發(fā)展及相應的通用計算平臺軟件標準的提出和深化，為各種傳統(tǒng)算法的并行優(yōu)化提供了新的基礎.基此，該文提出了一種基于CUDA的高維空間距離檢索算法，通過并行優(yōu)化空間距離計算及排序過程，借助最新的圖形硬件的并行運算能力，能極大提高檢索速度，在單機平臺上實現(xiàn)百萬級別的高維空間實時檢索以及極大推動各種相關領域的實時應用，如實時多媒體數(shù)據(jù)檢索，以及數(shù)據(jù)庫檢索.同時，算法能實現(xiàn)精確檢索，避免以往的優(yōu)化算法存在的數(shù)據(jù)依賴性和檢索結(jié)果的不穩(wěn)定性.

今后的研究，進一步利用硬件特性及優(yōu)化算法以提高并行效率，同時，研究有效策略減少數(shù)據(jù)維度非規(guī)則化（例如維度非2的N次冪）導致的效率下降.對于更高維的空間數(shù)據(jù)且存在大量0值的空間數(shù)據(jù)，將研究有效的數(shù)據(jù)壓縮方式，提高空間利用率和檢索效率.同時，在單GPU并行算法的研究基礎上，進一步研究多GPU并行運算技術，以實現(xiàn)億萬級別的實時高效檢索.

致謝：感謝圖酷科技公司的胡保坤、胡靜提供了部分性能測試結(jié)果.

［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，F(xiàn)aloutsos 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，F(xiàn)aloutsos 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近鄰查詢的高維索引結(jié)構(gòu)［J］.計算機研究與發(fā)展，2005，42（12）：2213－2218.

［13］莊毅，翁建廣，莊越挺，等.一種基于雙重距離尺度的高維索引結(jié)構(gòu)［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

中小企業(yè)創(chuàng)新基金項目（10C26213304161）；浙江省教育廳科研基金項目（Y200805962）.

周迪斌（1978—），男，江西安義人，講師，博士，貝德福德大學在職博士后，主要從事科學計算可視化和并行計算研究.E－mail：dibin.z＠163.com