[發明專利]高速并行數據查找方法

有效

• 申請號: 201710320330.2
• 申請日: 2017-05-09
• 公開（公告）號: CN108874799B
• 公開（公告）日: 2021-11-30
• 發明（設計）人: 叢楊;田冬英
• 申請（專利權）人: 中國科學院沈陽自動化研究所
• 主分類號: G06F16/2453
• 分類號: G06F16/2453
• 代理公司: 沈陽科苑專利商標代理有限公司 21002
• 代理人: 王倩

本發明涉及一種高速并行數據查找方法。首先為充分發揮硬件設備的并行處理能力，構建基于brute force的并行查詢器；離線階段將train集(查詢數據集)應用KD樹進行劃分，由leaf節點構建label集；在線階段對query集分批先送入上層并行查詢器查詢label集，結果緩存到leaf_buffer，隨后對已滿leaf_buffer使用下層并行查詢器。利用這種分層查找結構，實現了對大量數據的高效并行查找，可以廣泛應用于數據挖掘領域。

技術領域

本發明涉及一種高速并行數據查找方法，屬于數據挖掘領域。

背景技術

為了加快對數據的在線查找速度，目前已有方法包括局部敏感哈希、各種樹、隨機森林方法等。這些方法在離線階段對查詢數據集(train集)建立能夠表達數據在數據空間分布特點的模型，在線階段利用模型提供的已知信息加快查找速度，這樣的模型可能是數學表達式、樹形結構或網狀結構。KD樹方法通過建立樹形的連接關系大幅減少了在線查詢時數據距離的計算次數，從而提高了速度，在基于CPU的近鄰查找應用中被廣泛使用。

今年來，GPU和FPGA等并行運算設備得到了廣泛運用和飛速發展。基于GPU實現的brute force數據查找相對CPU實現有顯著效果提升，數據距離計算次數多是該方法速度提升的主要瓶頸。一些人探索將GPU并行能力與KD樹的優勢結合起來，然而GPU設備的應用強調大量數據處理步驟的高度的一致性，KD樹則強調對不同的數據采用不同的處理，這一本質分歧最終導致傳統的KD樹方法的并行化實現在查詢階段出現分支，導致執行效率低、速度慢。

發明內容

針對上述技術不足，本發明提供一種高速并行數據查找方法。該方法可以充分利用GPU、FPGA等硬件設備的并行運算能力并利用KD樹減少數據距離計算次數，從而實現速度的提高。

本發明解決其技術問題所采用的技術方案是：高速并行數據查找方法，包括以下步驟：

離線階段：分割train集,并創建label集；

在線階段：通過多層并行查詢器查label集、train集的子集，實現數據查找。

所述離線階段包括將train集劃分成多個節點，由每個節點內的數據子集train_leaf生成label集。

所述將train集劃分成多個節點具體為基于KD樹將train集劃分成多個leaf節點。

所述并行查詢器為基于brute force方法的并行查詢器。

所述并行查詢器的結果包括RNN和/或KNN的一個或多個。

所述在線階段：先用上層的并行查詢器查label集，結果緩存到節點緩存leaf_buffer，對已滿的leaf_buffer采用下層的并行查詢器查train集的子集。

所述在線階段包括以下步驟：

步驟(1)：首先將query集分批，每批處理q_num個query；

步驟(2)：為每個label分配一個節點緩存leaf_buffer，大小為b_num＝q_num+b_thres，b_thres為設定值，用于存放query的索引；

步驟(3)：將該批query與label集應用上層的并行查詢器查找結果，并將結果推送到leaf_buffer內；

步驟(4)：查詢所有leaf_buffer；如果leaf_buffer內個數超過_thres，則執行步驟(5)，否則執行步驟(3)；