Efficient distributed locality-sensitive hashing method

Abstract

A distributed locality-sensitive hashing method, comprising: loading original data from a distributed file system, reading a set of original data vectors, and generating a first elastic distributed data set; Quantity k, construct L composite hash functions; calculate L hash values ​​of each item of data in the data set, map each item of data to each hash bucket of each hash table, and convert the L hash values ​​of each item of data The key-value pair composed of the hash table identifier and the value of the composite hash function is merged into a character string and mapped to a digital key value, and the digital key value and the data identifier form a key-value pair, which is saved as a second elastic distributed data set; according to The digital key value of each data item in the second data set is repartitioned, so that data with the same digital key value is stored in the same partition, and the construction of the hash table is completed. The method can reduce the amount of shuffling generated in the process of constructing the hash table, improve the efficiency of constructing the index, and reduce the overhead of message transmission during query.

Description

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

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