基于局部敏感哈希的多維海量數據處理

張博文 張淑麗 郝昕 馬超

摘 要：針對多維海量的超精密加工機床狀態(tài)監(jiān)控數據難以被高效地存儲與查詢這一問題，文章提出了基于局部敏感哈希的多維海量數據處理方法。該方法利用P穩(wěn)定的局部敏感哈希算法，一方面對數據進行散列化存儲，使分散在各存儲節(jié)點上的數據在存取時避免了讀寫熱點；另一方面也實現(xiàn)了數據降維，通過其結果的碰撞操作，保證了各存儲節(jié)點內數據具有一定的近鄰性，這一性質以犧牲一定的查詢準確率為代價極大地縮小了查詢范圍，從而間接地提高了查詢效率。實驗結果表明，該處理方法可以有效的提高多維海量數據的存儲與查詢效率。

關鍵詞：多維海量數據；局部敏感哈希；數據降維

中圖分類號：TP315 文獻標志碼：A 文章編號：2095-2945（2019）02-0054-02

Abstract： In order to solve the problem that it is difficult to efficiently store and query the condition monitoring data of multi-dimensional and massive ultra-precision machining machine tools， a method of multi-dimensional massive data processing based on local sensitive Hash is proposed in this paper. In this method， P-stable local sensitive Hash algorithm is used， on the one hand， the data is hashed and stored， so that the data scattered on each storage node can avoid reading and writing hotspots， and on the other hand， the dimension reduction of the data is also realized. Through the collision operation of the results， the data in each storage node has a certain degree of adjacency， which greatly reduces the query range at the expense of certain query accuracy， and thus indirectly improving the query efficiency. The experimental results show that the method can effectively improve the efficiency of multi-dimensional massive data storage and query.

Keywords： multi-dimensional massive data； locally sensitive Hash； data dimensionality reduction

在超精密加工機床制造領域，加工機床的精度保持是加工過程中的監(jiān)測重點。但超精密加工機床具有物理結構復雜的特點，在加工過程中，加工精度會受震動、熱變形等物理因素影響[1]。因此，需要建立基于IOT技術的監(jiān)測系統(tǒng)來實時采集超精密加工機床的狀態(tài)監(jiān)控數據[2]。

1 局部敏感哈希算法

在多維海量數據處理領域中的眾多快速搜索算法中，應用最廣泛的算法是基于索引樹的搜索算法[3]。但是隨著數據維度的增多，任意兩點之間的最大距離與最小距離近似相等，這種情況會導致基于索引樹的搜索算法效率變低[4]。

Locality-sensitive hashing（LSH）局部敏感哈希算法多應用于處理多維海量數據的圖像搜索和網頁查找領域。LSH算法原理是基于兩點間的沖突性與兩點間的距離相關，兩點間距離越近，則沖突越大[5]。為此，本文將LSH算法應用在對多維海量的狀態(tài)監(jiān)控數據進行的存儲與多鍵查詢操作中。

LSH算法是隨機映射算法。在基于P穩(wěn)定分布的LSH算法中，哈希函數族是局部敏感的，因此在利用其對多維數據進行數據降維操作的同時，仍能有效的保持兩個多維數據之間的距離，可以將多維的數據映射到一個整數集。

根據P穩(wěn)定分布，從中產生一個隨機向量a和一個在[0，W]范圍內的隨機實數b。其中W是一個大的素數。

根據公式（1），可以計算得到向量的哈希值Ha，b（V）。通過選擇不同的基于P穩(wěn)定分布的向量分布來得出哈希值組G（V）={Ha1，b（V），Ha2，b（V）…}。

通過設置不同的整數權重，將向量V的哈希值組映射到一個單一索引T1中，其中P1是哈希表的大小，為一個大的素數。

選擇不同的權重，建立單一索引T2。

通過迭代執(zhí)行上述步驟，可以將一個高維向量V映射成L組（T1，T2），當兩個向量的T1和T2值相等時，則可以判斷這兩個向量臨近或相似。

2 基于LSH算法的數據存儲與查詢

在搭建數據存儲集群時，將數據存儲節(jié)點個數設置為K，接著計算各存儲節(jié)點的特征向量，記為特征向量組，然后根據公式（1），（2），（3），計算各特征向量對應的L組二元哈希值；與此同時，利用監(jiān)測系統(tǒng)實時采集最新的狀態(tài)監(jiān)控數據，接著根據公式（1），（2），（3），計算狀態(tài)監(jiān)控數據對應的L組二元哈希值；最后，將狀態(tài)監(jiān)控數據的二元哈希值與特征向量組的二元哈希值進行碰撞，得出碰撞集合。碰撞集合對應的數據節(jié)點內的數據在數據特征方面與狀態(tài)監(jiān)控數據存在相似性。因此，將狀態(tài)監(jiān)控數據存儲在碰撞集合的一個對應節(jié)點中。