基于CPU-GPU異構體系結構的并行字符串相似性連接方法

徐坤浩 聶鐵錚 申德榮 寇 月 于 戈

(東北大學計算機科學與工程學院 沈陽 110169)

(xukunhao725@163.com)

隨著傳統互聯網的發展和移動互聯網的出現，數據量迅速變大，“大數據”的概念逐漸被人們熟知.但大量的數據也對傳統的數據存儲和處理帶來了新的挑戰.為了更快地處理大數據，人們采用例如MapReduce和HDFS(Hadoop distributed file system)等分布式的策略來計算和存儲大數據.傳統的CPU性能提升方法已經達到瓶頸，提高主頻和核心數量等方法對CPU性能的提升變得越來越困難，僅由CPU負責計算的傳統相似性連接算法的處理速度已經漸漸滿足不了用戶的需求.近年來，GPU的處理性能和并行處理單元集成度提升迅速，更多的算術邏輯單元使得GPU的綜合計算性能遠超CPU.GPU能夠極大地解決CPU處理能力不足的問題，因此基于CPU-GPU異構體系結構的處理模式正成為未來的發展趨勢.

相似性連接處理技術是對來自不同數據集的2個對象計算相似度，并以相似度是否達到指定閾值作為對象間的連接條件.目前，相似性連接技術已經被廣泛地應用在搜索引擎、數據集成以及知識庫構建等領域.根據計算對象間相似度的算法不同，常見的相似性連接可以分為字符串相似性連接、集合相似性連接、向量相似性連接以及圖相似性連接，其中以字符串相似性連接應用最為廣泛.字符串的相似性可以通過Jaccard相似度等多種相似性度量進行計算.傳統的相似性連接處理技術一般使用過濾-驗證框架，包含過濾和驗證2個部分：在過濾階段設計高效的過濾算法將大量不可能符合相似度要求的數據記錄對過濾剔除，大幅減少候選對的數量；在驗證階段，計算每個候選對的相似度，將滿足相似度條件的候選對添加至最后結果.

目前，對相似性連接算法的優化主要集中在過濾階段的優化，通過對過濾算法的優化來提升過濾效果.現有研究工作提出了很多過濾算法，包括基于倒排索引的計數過濾算法[1]、基于位置的過濾算法[2]、基于長度的過濾算法[3]以及基于前綴的過濾算法[4].這些算法在一定程度上都提升了過濾階段的效率，但大部分都是基于串行處理的設計思想，處理效率受到了極大的限制.因此，本文主要研究通過CPU-GPU異構體系結構并行處理相似性連接算法，提高相似性連接算法的處理效率.由于CPU與GPU在計算模型上的巨大區別，傳統的相似性連接算法無法直接在GPU上直接運行.GPU強大的計算能力來源于大量的核心帶來的高并行度，通過大量核心并行的執行計算提高任務處理效率，但GPU存在不適合執行復雜邏輯控制的缺點.因此基于GPU實現相似性連接的加速處理，就必須根據GPU的處理架構特點設計相應的處理策略和優化方法.

本文主要研究基于CPU-GPU異構體系結構的并行相似性連接處理方法，通過將任務進行分解并運行在不同處理器架構上，提升任務并行性，從而提高基于過濾-驗證模型的相似性連接處理效率.本文的主要貢獻有4個方面：

1) 提出了基于CPU-GPU異構體系結構的并行相似性連接處理策略，充分利用GPU的并行計算能力和CPU的邏輯計算能力.

2) 提出了基于GPU的倒排索引結構和構建方法，并采用SoA(struct of arrays)結構提升并行計算時倒排索引的構建速度.

3) 提出了面向長度過濾和前綴過濾算法的GPU并行過濾方法，提高記錄對的過濾效率.

4) 通過對比實驗證明了所提出的并行算法可以有效地提升相似性連接中并行處理的執行效率，并分析了不同條件下算法的性能表現.

1 相關工作

目前，關于相似性連接技術的研究工作可以分為基于串行技術的方法和基于并行技術的方法.

基于串行的相似性連接研究主要集中在對匹配記錄對過濾算法的優化以及不同類型數據的相似性連接算法2個方面.Rong等人[4]提出了基于全局指令的多前綴過濾算法.這篇文章使用了流水線全局指令模式，并且提出適合這種模式的多前綴過濾算法，有效地減少在驗證階段需要計算的候選對數量.Cui等人[5]認為隨著數據實時性要求的提升，動態數據流會成為重要的數據來源，所以對數據流的數據相似性連接展開了研究，提出基于編輯距離和滑動窗口語義驗證的相似性連接算法，介紹了數據流中滑動窗口模型的構建以及特征提取等關鍵步驟.Wang等人[6]研究了局部相似性連接的問題，該文首先判斷2個字符串是否具有一定的局部相似度，然后設計算法定位二者的最長相似子串，基于局部相似子串的長度進行字符串的相似性連接.Zhao等人[7]對數組形式的數據的相似性連接進行研究，文章首先將數組數據抽象成高維向量，然后定義了向量的相似性連接定義與度量標準；在連接的基礎上進行了查詢優化，提供高效的查詢操作，并且將這種相似性連接與查詢的算法推廣至圖結構的數據.Patil等人[8]研究不確定字符串的相似性連接和查詢過程.以上的相關研究工作都局限在串行的相似性連接算法上，并沒有突破串行算法的性能瓶頸，而且針對特定結構數據的相似性連接算法并不具備良好的普適性.

在并行的相似性連接算法方面，近些年的研究主要集中在借助已有的并行計算框架以及利用GPU實現并行化2個方面.Chen等人[9]利用MapReduce實現相似性連接，文章提出基于聚類抽樣和KD樹(k-dimensional tree)的數據劃分方式，保證數據被平均地分配到節點上，然后提出基于順序映射和距離的過濾方式進行數據過濾，提升算法執行效率的同時也使算法具有良好的伸縮性.鄧詩卓等人[10]利用Spark框架和雙前綴過濾方法實現了相似性連接算法.Matsumoto等人[11]提出了并行排序算法，同時利用并行最大最小堆結構在CPU-GPU異構體系上實現了數據相似性連接.Johnson等人[12]利用GPU實現了k-NN算法以及相似性搜索算法，利用GPU進行并行的局部數據排序，壓縮數據集來減少數據傳輸與通信的代價.Feng等人[13]研究文檔相似性連接，針對文檔數據的特殊性和GPU計算的特點提出了2階段相似性連接算法，根據TF-IDF算法進行排序后對低頻詞進行過濾，提出適合并行計算的倒排索引讀取和相似度計算方法.

除此以外，GPU也被廣泛地應用到其他方面.Alam等人[14]設計適合GPU并行計算的cuPPA算法解決無標度網絡中遇到的問題，算法基于優先附著模型，并且可以通過Hash的方式支持多GPU同時計算.Doraiswamy等人[15]使用GPU構建索引來解決時空數據的查詢問題，索引覆蓋多個維度，采用塊存儲的形式加快數據查詢速度，并且同時支持基于異構體系結構的查詢請求.

與已有的工作相比，本文的工作將研究基于并行計算方式的相似性連接處理策略，突破傳統串行算法的性能瓶頸，設計面向GPU的數據匹配索引結構，以及利用GPU處理架構并行計算模型，提升單處理機上的并行處理能力，降低分布式環境的數據劃分和網絡通信代價.

2 基于CPU-GPU的相似性連接處理框架

2.1 相似性連接方法

本文的研究內容主要面向以文本為屬性內容的記錄集合間的相似性連接方法，其中記錄集合間的相似性度量主要采用基于字符串的相似性匹配方法.字符串相似性匹配方法可以分為2類：基于特征的相似性匹配和基于字符的相似性匹配，其中常用的相似性度量算法有Jaccard相似度、余弦相似度、遺傳相似度和編輯相似度等.本文將針對基于特征的相似性匹配方法相似性連接進行優化處理，為此首先給出相似性連接相關定義：

定義1.相似性連接.給定2個記錄集合R和S，r和s分別是來自R和S的記錄，Sim表示相似度計算函數；對于給定相似性閾值τ，相似性連接是指找出所有相似度大于τ的記錄對r,s，即集合：

{r,s∈R×S|Sim(r,s)≥τ}.

目前相似性連接最常用的處理框架是過濾-驗證框架.過濾-驗證框架分為記錄對過濾和相似度驗證2個步驟.過濾步驟主要的目的是過濾不相似的候選記錄對，減少候選記錄匹配集的大小.過濾算法的設計需要同時平衡過濾效果與過濾成本2個因素：想追求更好的過濾效果勢必會增加過濾成本；而簡單的過濾算法又會導致過濾效果不明顯，難以降低驗證階段的處理代價.

在過濾策略中可以使用索引結構提高過濾效率：例如對每個特征建立倒排索引，利用倒排索引的包含項生成候選對.目前，相似性連接在過濾階段最常用的算法是前綴過濾算法.前綴過濾算法的基本思想是利用前綴子串來衡量整體的相似性[16].其中，首先對所有的特征進行排序，然后對每一個字符串進行比較，如果其前綴部分的重疊程度小于設定的閾值，就將候選對刪除.前綴過濾常常與長度過濾和位置過濾等方法共同使用來達到更好的過濾效果.

驗證階段主要任務是精確計算所有候選對的相似度，如果記錄間的相似度大于給定閾值，那么該記錄對即可以作為連接結果輸出.

相似性連接算法不僅可以處理2個數據集合間的記錄相似性匹配，也可以用于在同一個數據集合執行自連接操作，從而發現集合中冗余記錄.

2.2 基于GPU的數據處理原理

隨著GPU處理器計算能力的提高，通用型GPU(general-purpose GPU， GPGPU)被廣泛地應用于高性能計算等領域.相關研究表明GPU在處理連接、排序、索引構建等過程時具有更優異的表現.常用的通用GPU計算框架包括NVIDIA的CUDA(compute unified device architecture)和非盈利性組織Khronos Group掌管的OpenCL.目前，多數的研究使用的是CUDA框架處理并行計算問題，該框架使GPU利用SIMT(single instruction multiple threads)體系結構解決復雜的計算問題.本文將基于CUDA框架在索引處理上的性能特性設計相似性連接的算法處理流程.

GPU的優勢在于眾多內核帶來的高并發度，然而并不是所有的計算任務都適合使用GPU計算.CPU適合處理控制密集型任務，GPU適合處理包含數據并行的計算密集型任務.因此GPU的并行處理并不是處理完整的計算流程，而是按照計算任務的特性進行劃分，GPU處理由計算任務主導的且帶有簡單控制流的計算任務.2種處理器在功能上互補，使CPU-GPU異構并行計算體系結構獲得最佳性能.

2.3 基于異構體系的相似性連接處理框架

傳統串行相似性連接方法可以分為數據讀取、倒排索引構建、原始數據過濾和相似度驗證4個主要步驟，其處理過程都是基于CPU處理計算，數據在主存中存儲.

基于CPU-GPU異構體系結構的處理方法將傳統方法的4個步驟分開處理，其中適合并行計算的部分由GPU負責，數據存儲在GPU顯存中；涉及復雜邏輯控制的部分由CPU負責，數據存儲在主存中；處理器之間通過PCIe(peripheral component interconnect express)通道進行數據傳輸.這種方式能充分利用CPU-GPU異構體系結構中2種處理器不同的數據處理特點，提高整體的執行效率.本文對傳統相似性連接方法的主要步驟進行分析和重新設計，如圖1所示.①使用CPU讀取數據，利用GPU并行構建倒排索引；②使用CPU依據倒排索引生成候選對；③使用GPU對候選對進行雙重長度過濾；④使用CPU驗證相似度得到最終結果集R. 2種處理器協同工作完成相似性連接整體任務.

Fig. 1 Similarity join algorithms based on theCPU-GPU heterogeneous architecture圖1 基于CPU-GPU異構體系的相似性連接算法

3 基于GPU的倒排索引構建方法

在相似性連接算法中，利用倒排索引可以快速找到可能相似的候選項，從而達到過濾不相似項的效果.倒排索引是大部分過濾算法的基礎，為此本文首先提出使用GPU構建倒排索引的方法.

相比于內存空間，GPU的存儲空間是很有限的，GPU全局內存(global memory， GM)一般只有幾GB的空間，而訪問速度更快的共享內存只有KB級別的空間，所以使用GPU生成倒排索引時必須考慮減小倒排索引的體積.同時，GPU與主機內存之間的消息通信必須通過PCIe通道，目前CPU從內存讀寫數據的速度是PCIe通道的4～8倍，所以需要盡可能對原始數據以及倒排索引進行壓縮，利用GPU存儲空間來存儲數據.出于以上的考慮本文采用了全局內存映射表來減小數據和索引的體積.

全局內存映射表的功能類似于數據字典，可以將體積較大的字符串類型的特征項轉換為數值類型的唯一序號.通過這種結構，倒排索引中每個鍵值對所占用的空間大幅減少，原始數據的體積也大幅減少，這樣就可以使用GPU全局內存存儲更多的原始數據以及索引信息.

基于這個問題，本文首先對傳統的倒排索引結構進行改進，采用基于SoA結構的倒排索引，充分利用GPU多線程并發訪問的特性，提升索引訪問和構建速度.SoA也被稱為并行結構體或者并行數組，這種數據結構的出現主要是為了解決在并行訪問的場景下傳統結構體數組訪問和寫入效率低的問題.圖2所示為SoA與AoS這2種數據結構的定義以及在內存中布局方式的對比，SoA為結構體中定義的每個屬性創建一個數組，相同的屬性值在內存中連續存放，不同的數據之間沒有任何耦合.所以這種數據結構非常適合多線程同時并發訪問，并且全部由基本數據類型組成的數組在訪問時也不需要進行數據補全.

Fig. 2 Comparison of SoA and AoS structure圖2 SoA與AoS結構對比

GPU最大的優勢在于多線程并行計算的能力.為了充分地提高并行度，每個線程塊block將負責一部分原始數據的解析工作，block中的每個線程每次會讀取一個單詞，根據全局映射表解析數據生成tid,sid，然后查找全局倒排索引，使用函數atomicAdd將sid和tid分別寫入對應的位置，等到所有線程完成各自的任務后，SoA型倒排索引的構建工作也就完成了.如果想要進一步提高索引的讀寫速度，可將得到的全局倒排索引按照共享內存的大小順序劃分，劃分后的部分索引傳入共享內存中等待后續使用.將構建完成的索引回傳至主存，然后對tid相同的匹配對進行合并就得到了通用性更好的傳統倒排索引.算法1表述了基于GPU的倒排索引的構建過程.

算法1.基于GPU的倒排索引構建算法.

輸入：字符串集S;

輸出：倒排索引ISoA.

① 初始化：

② 基于字符串集S構建全局映射表Map；

③ 為字符串集S中每個token創建特征編號tid，為每個字符串創建編號sid;

④ 記錄數據集中token的數量N;

⑤ 將S和Map加載到全局內存；

⑥ 初始化SoA結構的倒排索引ISoA；

⑦ for eachS中的字符串si并行執行操作：

⑧ 創建字符串si的token集合Tsi；

⑨ for eachTsi中的token并行執行操作：

⑩ 基于Map解析數據生成tid,sid；

算法1中行①～④是在CPU和主存上做的準備工作，主要包括數據讀取、構建全局內存映射表Map等.行⑤～⑥將數據和映射表通過PCIe通道傳輸至GPU全局內存并且初始化大小SoA型倒排索引結構.行⑦～為具體的并行倒排索引構建過程，圖3對這一過程進行了簡要的描述.對于每條數據使用一定數量的線程并行解析，根據全局內存映射表Map解析tid,sid，使用atomicAdd函數并行補全SoA倒排索引.行將處理得到的SoA倒排索引回傳至主存，因為并行計算得到的倒排索引是SoA類型，行～在CPU上對倒排索引進行合并，得到傳統的AoS類型的倒排索引.合并后的倒排索引具有更高的普適性和更廣泛的應用場景，可應用到搜索引擎、數據清洗等方面.

Fig. 3 Construction process of inverted index圖3 倒排索引構建過程

4 基于CPU-GPU的并行相似性連接方法

長度過濾的基本思想是：如果字符串s與r相似，則其長度一定不會相差太多.以Jaccard相似度為例，給出長度過濾算法中字符串長度與相似度閾值的關系.長度過濾因計算簡單，且條件僅僅需要統計每條數據項的長度等特點被廣泛地應用到過濾-驗證框架中，同時這種邏輯簡單的計算密集型過濾算法特別適合GPU并行計算.因此本文考慮使用基于GPU的長度過濾算法對原始數據集進行過濾：

(1)

其中，τ為已定義的相似度閥值.如果數據集中的字符串是由許多特征組成的，那么除了使用字符串的長度進行長度過濾之外，還可以使用每個字符串的特征數量進行過濾.因為數據集中普遍存在長度相近，但是所含單詞數量相差很多的字符串，僅使用數據長度無法過濾掉這些不相似的字符串.而使用長度和特征數雙重過濾的方式可以過濾掉這一類型的字符串，進一步提升過濾效果減少候選項的數量.長度過濾算法的主要過程是統計每個字符串的長度，以及判斷字符串的長度是否在相似度閾值規定的區間內.這2個步驟是2個完全獨立的工作，并且這2部分工作都是簡單的讀寫任務，不涉及復雜的邏輯處理，因此十分適合使用GPU對這部分工作進行并行化處理.

長度過濾算法也有缺點，例如對相似度閾值敏感、對方差較小的短文本數據集過濾效果很差等.為了彌補長度過濾算法的缺點，本文使用前綴過濾與長度過濾相結合的方式進行數據過濾.

前綴過濾算法是目前比較領先的過濾算法之一，并且常常與長度過濾等方法一起使用來獲得更好的過濾效果.前綴過濾的基本思想是：對于已按照某種規則排序后的數據項，如果2個數據項的前p項特征中有相同項，那么這2個數據項就可能相似.前綴長度p與字符串長度|s|以及相似度閾值τ的關系：

(2)

使用前綴過濾算法對經過長度過濾之后生成的中間結果集進行2次過濾：對于中間結果集中的每個候選項，根據相似度計算公式計算出前綴p，然后判斷候選項是否出現在前綴項對應的倒排索引中.經過前綴過濾之后的中間結果集被進一步減小，從而也少了后續相似度驗證階段的任務量.

基于以上考慮，本文首先使用算法1，利用GPU構建倒排索引；然后使用GPU對原始數據集進行雙重長度過濾生成中間結果集；隨后根據倒排索引，使用前綴過濾算法對中間結果集進行2次過濾，剔除不滿足前綴過濾要求的候選項；最后對通過2次過濾的候選項逐個進行相似度驗證，將通過驗證的候選項添加至最終結果.以Jaccard相似度為例，算法2描述了使用倒排索引基于前綴過濾和長度過濾思想的并行相似性連接算法.

算法2.并行相似性連接算法.

輸入：字符串集S、相似度閾值τ、相似性度量函數Sim;

輸出：相似字符串匹配集RM.

① 使用算法1創建SoA結構倒排索引ISoA；

② 設置RM=?，創建全局字符串token映射表TS和長度表LS，初始化候選匹配對集合Candi；

③ for eachS中的字符串si并行執行

④ 使用atomicAdd函數對si中的每個token執行操作以在TS和LS中記錄si的token數量和特征長度：

⑤ end for

⑥ for eachS中排序后的字符串si并行執行操作：

⑦low=τ|si|,high=|si|τ,min=τTS[si],max=TS[si]τ;

⑧ 對于S中其他的字符串sj，如果滿足|sj|∈[low,high]且TS[sj]∈[min,max]，則添加候選匹配對(sj,si)至Candi；

⑨ end for

⑩ for each候選對(sj,si)∈Candi執行

算法2中行①依據算法1使用GPU并行構建倒排索引，行②進行相關結構的初始化.行③～⑤解析數據統計每個字符串的長度以及所含特征的數量.行⑥～⑨使用GPU對原始數據集進行雙重長度過濾，根據給定的相似度閾值τ計算出長度和特征數范圍，將同時滿足長度和特征數量要求的記錄對添加至中間結果集.行⑩～對中間結果集進行前綴過濾，將同時滿足2種過濾條件的候選項添加至候選結果集中.行在CPU上對候選結果集中所有候選項進行相似度驗證，將相似度超過閾值τ的候選項添加至匹配結果集.

5 實驗結果與分析

5.1 實驗設置與數據集

本次實驗采用多種不同類型的數據集，表1給出了本次實驗所用數據集的基本信息.

Table 1 Datasets for Experiments表1 實驗所用數據集

1) DBLP.從DBLP(database systems and logic programming)原始數據集中抽取作者名和論文名進行拼接，然后隨機刪除、更改后形成的數據集.

2) AOL.AOL(american online)搜索引擎的查詢日志，該數據集中的每一行代表一組查詢關鍵詞.

3) Querylog.某搜索引擎的查詢語句集合.

4) BMS.商業管理系統(business management systems， BMS)的某商店使用POS機記錄的銷售數據.

5) Enron.真實的電子郵件數據集，一個字符串代表一個真實的電子郵件的信息，平均長度很長.

本文實驗主要測試算法的執行時間、加速比、算法各部分占比以及數據集大小、相似度閾值等條件對算法的影響.實驗環境：本文實驗所用GPU：NVIDIA GTX 1060 6 GB；CPU：Intel Core i7-8700 3.20 GHz；內存：8 GB；操作系統：Windows 10.算法使用CUDA 9.0和C++實現.

5.2 實驗結果與分析

本文將通過實驗分別檢測GPU加速在倒排索引構建階段和相似性連接整體執行上的加速效果.

1) 基于GPU的倒排索引構建方法的作用

表2記錄了分別使用GPU和CPU在不同數據集上構建倒排索引時程序的執行時間.可以明顯地看出使用GPU構建倒排索引可以大幅提升倒排索引的構建速度.在不同的數據集上，本文提出的基于GPU的SoA型倒排索引的構建方法的加速比(并行算法與串行算法執行時間的比值)分別達到了51.87，8.53，81.40，23.83，80.58，加速效果明顯.

在Enron，DBLP，BMS這3個數據集上獲得了較高的加速比，而在Querylog數據集上的加速比相對較低.這是因為Querylog是小數據集，數據集較小時并行計算帶來的計算速度的提升效果不明顯，同時GPU的引入會提升數據傳輸的代價，所以加速比相對較低.而同樣是小數據集的BMS是純數字數據集，數字類型占據空間相對較小，所以體量更小的BMS數據集的數據規模其實比Querylog數據集更大，因此使用GPU構建倒排索引的加速效果也比較明顯.在使用CPU構建倒排索引時需要使用Enron等較大數據集是因為并行計算大幅減少數據處理時間，所以加速效果十分明顯.

Table 2 Comparison of Inverted Index Construct Time表2 倒排索引構建時間對比

Fig. 4 Impact of dataset size on execution time圖4 數據集大小對執行時間的影響

圖4(a)記錄了使用GPU構建倒排索引時方法的執行時間隨數據集大小的變化情況，圖4(b)記錄了并行方法加速比隨數據集大小的變化情況.隨著數據集的增大，基于GPU的并行索引構建方法的執行時間呈近似線性增長.這是因為SoA結構保證不同線程間的讀寫沒有耦合，數據集的增大僅僅會增加單個線程完成計算任務需要的次數.加速比隨著數據集的增大逐漸提升，說明傳統的索引構建方法不能在數據集增大的同時保證運行時間的線性增長.因此本文提出的倒排索引構建方法可以在數據集規模較大的時候依然保證良好的執行效率，并且數據集越大構建方法的加速效果越明顯.

Fig. 5 Time proportion of each part of inverted index construction algorithm圖5 倒排序索引構建算法各部分時間占比

圖5比較了使用GPU構建倒排索引的過程中方法各部分的時間占比.其中預處理部分包括原始數據讀取與全局映射表構建2個步驟；GPU構建索引部分同時也包括主存與全局內存之間數據傳輸過程；CPU索引合并部分是指將SoA型倒排索引合并成通用的倒排索引結構的過程.在不同數據集上的實驗表明：數據預處理部分的時間占比最高，并且隨著數據集體積的增大，這部分的時間占比會進一步提高；而并行計算以及索引合并2個階段的時間占比很低.所以在CPU-GPU異構體系結構的倒排索引構建方法中，方法的性能瓶頸主要在CPU端的數據預處理部分.

2) 基于GPU的相似性連接方法的作用

表3記錄在不同數據集上進行實驗的結果，對比的串行算法為目前效率較高且適用范圍較廣的PPJoin算法[17].為了節省算法的執行時間，本節實驗分別從Enron，DBLP，AOL這3個數據集中抽取了24 000，60 000，140 000條數據進行實驗.實驗結果表明本文提出的基于CPU-GPU異構體系結構的算法相較于原有算法有一定的提升，在AOL數據集上獲得了最高45.6%加速效果，整體加速效果與倒排索引構建方法相比很不明顯.

Table 3 Comparison of Algorithm Execution Time表3 算法執行時間對比

Fig. 6 Execution time of the algorithm with differentdata scales圖6 算法在不同數據規模下的執行時間

Fig. 7 Time proportion of each part of similarity join algorithm圖7 相似性連接算法各部分時間占比

為了探究相似性連接方法加速效果及相關影響因素，本文記錄了通過實驗對比算法各個部分的時間占比隨數據集大小的變化情況，實驗結果如圖6和圖7所示.圖6展示了Enron，DBLP，AOL這3個數據集在不同數據記錄數量規模下的執行時間變化情況，從實驗結果可見，隨著數據規模的增大，算法的執行時間呈近似線性增長.圖7展示了Enron，DBLP，AOL這3個數據集在不同數據記錄數量規模下的算法各部分執行時間占比，從實驗結果圖可以看出使用GPU執行的創建索引(create index)和過濾記錄對(filter pairs)這2個階段的時間占比較低，隨數據集的變大逐漸減少或保持平穩；而相似度驗證記錄對(verify pairs)階段時間占比最高，超過了其余步驟的總和，并且隨著數據集的增大不斷增大.因此，最后在CPU端執行的相似度驗證階段是本文提出的相似性連接方法加速效果不明顯的主要原因，要進一步提升算法的加速效果，必須重新設計適合GPU并行計算的相似度計算方法.

圖8和圖9分別比較了相似度閾值τ對算法執行時間和過濾效果的影響.隨著相似度閾值的增加，候選項的數量以及算法的整體執行時間成近似線性減少，算法的過濾效果良好.其中DBLP數據集對閾值變化最敏感，因為此數據集中字符串長度方差最大，所以使用前綴過濾和長度過濾時提升相似度閾值可以大幅減少候選項的數量，迅速減少算法執行時間.

Fig. 8 Effect of similarity threshold on execution time圖8 相似度閾值對算法執行時間的影響

Fig. 9 Influence of similarity threshold on candidatefiltration圖9 相似度閾值對算法過濾效果的影響

通過本節實驗可以得出2個結論：

1) 使用GPU構建倒排索引可以明顯加快索引的構建速度，并且數據集數據量越大，算法的加速效果越明顯；

2) 基于CPU-GPU異構體系結構的并行相似性連接方法過濾效果良好，與傳統方法相比具有一定的加速效果.

6 總結與展望

本文提出了基于CPU-GPU異構體系結構的倒排索引構建方法以及相似性連接方法.采用SoA型的倒排索引結構加快并行條件下索引的讀寫速度，在獲得較高加速比的同時保證索引具有良好的通用性.基于前綴和長度過濾的并行相似性連接方法在一定程度上進一步提升了傳統方法的執行速度，并且為相似性連接算法的研究提供了一個新的思路.但是本文提出的方法依然存在局限性，實驗結果表明數據讀取和相似度驗證的2個階段時間占比較高，如果可以使用例如直接尋址等技術讀取數據并且構建適合GPU并行計算的相似性度量，就可以進一步提升方法的執行速度.下一步，我們將試圖在本文的基礎上解決這一問題.