基于局部敏感哈希的多维海量数据处理

张博文 张淑丽 郝昕 马超

摘 要：针对多维海量的超精密加工机床状态监控数据难以被高效地存储与查询这一问题，文章提出了基于局部敏感哈希的多维海量数据处理方法。该方法利用P稳定的局部敏感哈希算法，一方面对数据进行散列化存储，使分散在各存储节点上的数据在存取时避免了读写热点；另一方面也实现了数据降维，通过其结果的碰撞操作，保证了各存储节点内数据具有一定的近邻性，这一性质以牺牲一定的查询准确率为代价极大地缩小了查询范围，从而间接地提高了查询效率。实验结果表明，该处理方法可以有效的提高多维海量数据的存储与查询效率。

关键词：多维海量数据；局部敏感哈希；数据降维

中图分类号：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

在超精密加工机床制造领域，加工机床的精度保持是加工过程中的监测重点。但超精密加工机床具有物理结构复杂的特点，在加工过程中，加工精度会受震动、热变形等物理因素影响[1]。因此，需要建立基于IOT技术的监测系统来实时采集超精密加工机床的状态监控数据[2]。

1 局部敏感哈希算法

在多维海量数据处理领域中的众多快速搜索算法中，应用最广泛的算法是基于索引树的搜索算法[3]。但是随着数据维度的增多，任意两点之间的最大距离与最小距离近似相等，这种情况会导致基于索引树的搜索算法效率变低[4]。

Locality-sensitive hashing（LSH）局部敏感哈希算法多应用于处理多维海量数据的图像搜索和网页查找领域。LSH算法原理是基于两点间的冲突性与两点间的距离相关，两点间距离越近，则冲突越大[5]。为此，本文将LSH算法应用在对多维海量的状态监控数据进行的存储与多键查询操作中。

LSH算法是随机映射算法。在基于P稳定分布的LSH算法中，哈希函数族是局部敏感的，因此在利用其對多维数据进行数据降维操作的同时，仍能有效的保持两个多维数据之间的距离，可以将多维的数据映射到一个整数集。

根据P稳定分布，从中产生一个随机向量a和一个在[0，W]范围内的随机实数b。其中W是一个大的素数。

根据公式（1），可以计算得到向量的哈希值Ha，b（V）。通过选择不同的基于P稳定分布的向量分布来得出哈希值组G（V）={Ha1，b（V），Ha2，b（V）…}。

通过设置不同的整数权重，将向量V的哈希值组映射到一个单一索引T1中，其中P1是哈希表的大小，为一个大的素数。

选择不同的权重，建立单一索引T2。

通过迭代执行上述步骤，可以将一个高维向量V映射成L组（T1，T2），当两个向量的T1和T2值相等时，则可以判断这两个向量临近或相似。

2 基于LSH算法的数据存储与查询

在搭建数据存储集群时，将数据存储节点个数设置为K，接着计算各存储节点的特征向量，记为特征向量组，然后根据公式（1），（2），（3），计算各特征向量对应的L组二元哈希值；与此同时，利用监测系统实时采集最新的状态监控数据，接着根据公式（1），（2），（3），计算状态监控数据对应的L组二元哈希值；最后，将状态监控数据的二元哈希值与特征向量组的二元哈希值进行碰撞，得出碰撞集合。碰撞集合对应的数据节点内的数据在数据特征方面与状态监控数据存在相似性。因此，将状态监控数据存储在碰撞集合的一个对应节点中。