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

基于局部敏感哈希的多维海量数据处理张博文张淑丽郝昕马超摘要：针对多维海量的超精密加工机床状态监控数据难以被高效地存储与查询这一问题，文章提出了基于局部敏感哈希的多维海量数据处理方法。该方法利用P稳定的局部敏感哈希算法，一方面对数据进行散列化存储，使分散在各存储节点上的数据在存取时避免了读写热点；另一方面也实现了数据降维，通过其结果的碰撞操作，保证了各存储节点内数据具有一定的近邻性，这一性质以牺牲一定的查询准确率为代价极大地缩小了查询范围，从而间接地提高了查询效率。实验结果表明，该处理方法可以有效的提高多维海量数据的存储与查询效率。关键词：多维海量数据；局部敏感哈希；数据降维中图分类号：TP315文献标志码：A文章编号：2095-2945（2019）02-0054-02Abstract：Inordertosolvetheproblemthatitisdifficulttoefficientlystoreandquerytheconditionmonitoringdataofmulti-dimensionalandmassiveultra-precisionmachiningmachinetools，amethodofmulti-dimensionalmassivedataprocessingbasedonlocalsensitiveHashisproposedinthispaper.Inthismethod，P-stablelocalsensitiveHashalgorithmisused，ontheonehand，thedataishashedandstored，sothatthedatascatteredoneachstoragenodecanavoidreadingandwritinghotspots，andontheotherhand，thedimensionreductionofthedataisalsorealized.Throughthecollisionoperationoftheresults，thedataineachstoragenodehasacertaindegreeofadjacency，whichgreatlyreducesthequeryrangeattheexpenseofcertainqueryaccuracy，andthusindirectlyimprovingthequeryefficiency.Theexperimentalresultsshowthatthemethodcaneffectivelyimprovetheefficiencyofmulti-dimensionalmassivedatastorageandquery.Keywords：multi-dimensionalmassivedata；locallysensitiveHash；datadimensionalityreduction在超精密加工机床制造领域，加工机床的精度保持是加工过程中的监测重点。但超精密加工机床具有物理结构复杂的特点，在加工过程中，加工精度会受震动、热变形等物理因素影响[1]。因此，需要建立基于IOT技术的监测系统来实时采集超精密加工机床的状态监控数据[2]。1局部敏感哈希算法在多维海量数据处理领域中的众多快速搜索算法中，应用最广泛的算法是基于索引树的搜索算法[3]。但是随着数据维度的增多，任意两点之间的最大距离与最小距离近似相等，这种情况会导致基于索引树的搜索算法效率变低[4]。Locality-sensitivehashing（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算法