張博文 張淑麗 郝昕 馬超

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

關(guān)鍵詞：多維海量數(shù)據(jù)；局部敏感哈希；數(shù)據(jù)降維

中圖分類號：TP315 文獻(xiàn)標(biāo)志碼：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

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

1 局部敏感哈希算法

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

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

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

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

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

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

選擇不同的權(quán)重，建立單一索引T2。

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

2 基于LSH算法的數(shù)據(jù)存儲與查詢

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