[發明專利]高效分布式局部敏感哈希方法

有效

• 申請號: 201710422330.3
• 申請日: 2017-06-07
• 公開（公告）號: CN107391554B
• 公開（公告）日: 2021-10-01
• 發明（設計）人: 張萬新;李東升;徐穎
• 申請（專利權）人: 中國人民解放軍國防科學技術大學
• 主分類號: G06F16/22
• 分類號: G06F16/22;G06F16/2458;G06F16/2453;G06F16/2455
• 代理公司: 北京安博達知識產權代理有限公司 11271
• 代理人: 徐國文

一種分布式局部敏感哈希方法，包括：從分布式文件系統加載原始數據，讀取原始數據向量集合，生成第一彈性分布式數據集；根據用戶指定的哈希表數量L和哈希函數數量k，構造L個復合哈希函數；計算數據集中每項數據的L個哈希值，將每項數據分別映射到每個哈希表的各一個哈希桶中，將每項數據中的哈希表標識與復合哈希函數的值組成的鍵值對合并為字符串并映射為數字鍵值，數字鍵值與數據標識形成鍵值對，保存為第二彈性分布式數據集；根據第二數據集中每項數據的數字鍵值進行重分區，使得有具有相同數字鍵值的數據被保存在相同的分區中，完成哈希表的構建。該方法能減少構建哈希表過程產生的混洗量，提高構建索引效率，查詢時能減少消息傳遞開銷。

技術領域

本發明屬于互聯網技術中的大數據數據挖掘領域，特別是涉及局部敏感哈希方法的分布式實現，加速海量高維數據的相似性搜索。

背景技術

相似性搜索是多媒體信息檢索領域中的一個重要問題，是指根據用戶輸入的查詢對象，基于某種相似度(或距離)度量方式，在已有的數據集合中查找與之相似度最高(或距離最小)的對象。為了提升相似性搜索的效率，已有KD-tree、R-tree、SR-tree等索引方法被相繼被提出，并在低維空間中有良好的效果。但隨著數據維度的增加，這些方法的性能則呈現急劇下降的趨勢，該問題被稱之為“維度災難”。為了克服“維度災難”，許多近似搜索的方法被提出，其中最著名的方法之一就是局部敏感哈希(LocalitySensitiveHashing，LSH)。LSH方法通過使用一組具有局部敏感性質的哈希函數，會以很高的概率將原始數據空間中距離相近的對象散列到相同的哈希桶之中，查詢時則只需計算查詢對象所在哈希桶中的數據對象與查詢對象之間的距離即可找出近似點。

在搜索過程中，對于給定的一個特征，重要的是如何快速地從海量的特征中找到和這個特征相似的一些特征。局部敏感哈希就是：如果原來的數據相似，那么hash以后的數據也保持一定的相似性。數據的維數在某種程度上能反映其信息量，一般來說維數越多，其反映的信息量就越大。如果我們知道的信息越多，就能越準確地判定兩個東西的相似性。但因為高維空間上計算復雜度太高，所以通常是通過哈希函數把高維數據映射到低維空間上，降維就在某種程度上造成的信息的丟失，在降維后的低維空間中就很難100％保持原始數據空間中的相似性，所以是說“保持一定的相似性”。局部敏感哈希的基本思想是，用hash的方法把數據從原空間哈希到一個新的空間中，使得在原始空間的相似的數據，在新的空間中也相似的概率很大，而在原始空間中不相似的數據，在新的空間中相似的概率很小。這種方法以犧牲一部分精度為代價，大大降低了計算的復雜度，提高了高維空間中相似性搜索的效率。

盡管LSH已經成為近似相似性搜索領域中最重要的索引技術之一，但是該方法的常見形式都局限于單機計算環境，難以處理大規模數據，需要將該方法擴展到分布式環境下以處理海量數據。分布式環境下，一種直觀的方法是基于一系列通用分布式計算框架實現局部敏感哈希方法。ApacheSpark是目前最常用的分布式計算框架之一，相比于Hadoop等框架有著明顯的性能優勢。Spark的核心是彈性分布式數據集(RDD)，它是一種對分布式存儲的數據的抽象，本質是一組數據分片(partition)，每個分片包含一個或者多個數據項，不同分片上的數據項可被并行操作。在RDD之上，Spark提供了豐富的算子，如map，filter等，可以對RDD中的數據進行轉換和抽取。Spark的采用的是一種類HadoopMapReduce的計算模式。在MapReduce模式中計算過程分為map和reduce兩個階段，map階段將輸入的元素列表中的每一個獨立元素進行制定的操作，得到一組中間數據組成的列表；reduce階段則是對中間數據列表中的元素進行適當的合并和計算。而map階段與reduce階段之間傳遞中間結果的過程稱作混洗(shuffle)。混洗過程中map階段的中間結果會先寫入到本地磁盤，然后reduce階段不同節點跨網絡讀取中間結果數據。因此混洗通常是MapReduce類任務中最耗時的過程。