[發明專利]一種面向大規模數據的自適應最近鄰查詢方法

有效

• 申請號: 201811298577.X
• 申請日: 2018-11-02
• 公開（公告）號: CN109634952B
• 公開（公告）日: 2021-08-17
• 發明（設計）人: 任艷多;錢江波;孫瑤;胡偉
• 申請（專利權）人: 寧波大學
• 主分類號: G06F16/22
• 分類號: G06F16/22;G06F16/2458
• 代理公司: 寧波奧圣專利代理有限公司 33226
• 代理人: 程天鵬

本發明公開了一種面向大規模數據的自適應最近鄰查詢方法，特點是首先獲取包含多個原始大規模數據的數據集并給定查詢點，通過包含k次AND操作和L次OR操作的局部敏感哈希方法將原始數據集構造成若干個子數據集，然后學習得到與每個子數據集對應的哈希編碼，然后將所有哈希編碼按序排列得到所有子數據集的編碼索引，再獲取查詢點在每個子數據集下的查找表，接下來獲取查詢點在對應的子數據集下的候選集并融合，得到對給定的查詢點的最近鄰查詢結果；這種子數據集的構造方式能更好地挖掘數據集分布的信息，最大限度地降低了編碼的冗余，提升了對給定的查詢點的最近鄰查詢過程的查詢精度和查詢效率。

技術領域

本發明涉及信息檢索技術領域，尤其是一種面向大規模數據的自適應最近鄰查詢方法。

背景技術

目前，哈希技術是大規模數據檢索的一種有效解決方案。相關技術中，對整個數據集，采用統一的哈希編碼方式，得到的哈希編碼的長度也是一致的。但實際大規模數據中，數據集的分布沒有規律性。相關哈希技術沒有充分地利用數據集的分布信息，有待改進。

發明內容

本發明所要解決的技術問題是提供一種面向大規模數據的自適應最近鄰查詢方法，該方法能夠根據數據集分布的密度大小將其量化為不同長度的哈希編碼，有效減少數據集的編碼冗余，提高檢索準確性。

本發明解決上述技術問題所采用的技術方案為：一種面向大規模數據的自適應最近鄰查詢方法，包括以下步驟：

①獲取包含多個原始大規模數據的原始大規模數據集并給定查詢點，通過包含k次AND操作和L次OR操作的局部敏感哈希方法將原始大規模數據集構造成2^k個子數據集，通過k次AND操作和L次OR操作將查詢點映射到2^k個子數據集中，得到查詢點在每個子數據集中對應的映射數據；

②根據每個子數據集的大小從大到小對所有子數據集進行排序得到排序后的數據集，并對排序后的數據集中的每個子數據集設置一個與該子數據集的大小呈線性相關的編碼長度；

③將每個子數據集分別映射到乘積空間，通過最小化哈希編碼和原始數據的誤差的方法學習得到與每個子數據集對應的哈希編碼，然后將所有哈希編碼按照對應的子數據集在排序后的數據集中的順序對應排列得到所有子數據集的編碼索引；

④根據所有子數據集的編碼索引，在每個子數據集中對查詢點在每個子數據集中對應的映射數據按最近距離量化映射，得到查詢點在每個子數據集下的查找表；

⑤根據子數據集的編碼索引和查詢點在每個子數據集下的查找表，分別獲取在子數據集的編碼索引中離每個子數據集下的查找表的海明距離最近的與該查找表對應的最近鄰點集，并將每個最近鄰點集作為查詢點在對應的子數據集下的候選集；

①將查詢點對應的所有子數據集空間下的候選集進行融合，將融合后的數據集作為對給定的查詢點的最近鄰查詢結果，完成對給定的查詢點的最近鄰查詢過程。

所述的k次AND操作的具體過程為：根據原始大規模數據集特征及查詢精度的需求確定局部敏感哈希函數個數k，并根據局部敏感哈希函數族構建k個哈希函數，對所有原始大規模數據集中的每個原始大規模數據分別通過k個哈希函數進行映射，將原始大規模數據集劃分至2^k個子空間，然后按每個子空間中存在的數據數量對子空間降序排序，得到與原始大規模數據集對應的2^k個經過降序排序后的子數據集；L次OR操作的具體過程為：將上述k次AND操作執行L次，每次取k個不同的局部敏感哈希函數，最終得到L組不同的2^k個經過降序排序后的子數據集，然后將L組不同的2^k個經過降序排序后的子數據集按融合因子β進行融合得到最終的2^k個子數據集，其中，rank表示子數據集在對應的一組2^k個經過降序排序后的子數據集中的排序序號，jac表示jaccard相似系數。