Efficient distributed locality sensitive Hashing method

Abstract

The invention provides a distributed locality sensitive Hashing method. The method comprises the steps that original data is loaded from a distributed file system, an original data vector set is read, and a first elastic distributed dataset is generated; L composite Hash functions are constructed according to the number L of Hash tables and the number k of Hash functions designed by a user; L Hash values of each piece of data in the dataset are calculated, each piece of data is mapped into one Hash bucket of each Hash table, key value pairs composed of Hash table identifiers in all the data and values of the composite Hash functions are merged into a string, the string is mapped into digital key values, the digital key values and data identifiers form key value pairs, and the key value pairs are saved as a second elastic distributed dataset; and repartitioning is performed according to the digital key value of each piece of data in the second dataset, so that data with the same digital key value is saved in the same partition, and construction of the Hash tables is completed. Through the method, the shuffle amount generated in the Hash table construction process can be reduced, index construction efficiency can be improved, and message transmission overhead can be reduced during query.

Description

technical field [0001] The invention belongs to the field of big data data mining in Internet technology, in particular to the distributed realization of a local sensitive hash method, which accelerates the similarity search of massive high-dimensional data. Background technique [0002] Similarity search is an important problem in the field of multimedia information retrieval. It refers to finding the highest similarity (or object with the smallest distance). In order to improve the efficiency of similarity search, KD-tree, R-tree, SR-tree and other indexing methods have been proposed one after another, and they have good results in low-dimensional space. However, as the dimensionality of the data increases, the performance of these methods shows a sharp decline, a problem known as the "curse of dimensionality". To overcome the "curse of dimensionality", many approximate search methods have been proposed, one of the most well-known methods is Locality Sensitive Hashing (L...

AI Technical Summary

Problems solved by technology

[0007] Aiming at solving the similarity search problem of massive high-dimensional data, the present invention implements an efficient distributed local sensitive hashing method based on the Spark platform

Images