基于局部敏感哈希的多維海量數(shù)據(jù)處理

張博文 張淑麗 郝昕 馬超

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

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

中圖分類號(hào)：TP315 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：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ī)床的精度保持是加工過(guò)程中的監(jiān)測(cè)重點(diǎn)。但超精密加工機(jī)床具有物理結(jié)構(gòu)復(fù)雜的特點(diǎn)，在加工過(guò)程中，加工精度會(huì)受震動(dòng)、熱變形等物理因素影響[1]。因此，需要建立基于IOT技術(shù)的監(jiān)測(cè)系統(tǒng)來(lái)實(shí)時(shí)采集超精密加工機(jī)床的狀態(tài)監(jiān)控?cái)?shù)據(jù)[2]。

1 局部敏感哈希算法

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

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

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

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

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

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

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

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

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

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