K nearest neighbor approximation query method based on multi-layer locality sensitive hashing

Abstract

The invention belongs to the field of data analysis, and relates to a k nearest neighbor approximation query method based on multi-layer local sensitive hashing. The method comprises the following steps: firstly evaluating the number of data points mapped to each hash bucket, determining an overload hash bucket and an underload hash bucket according to the number of the data points in each hash bucket, then further hashing and dividing the overload hash bucket into a plurality of sub-buckets, and merging the underload hash buckets at the same time; and recursively performing re-hashing on thesub-buckets which are still overloaded after re-division, and balancing the sizes of the plurality of hash buckets as much as possible after multiple times of re-hashing. Therefore, the LSH index structure becomes a multi-layer tree-like structure. According to the method, the initially constructed LSH hash table is reconstructed, so that the kNN search efficiency of the query points in the denseregion and the kNN search accuracy of the query points in the sparse region are improved. The hash buckets in the multi-layer local sensitive hash structure are relatively uniform in size distribution, and the advantages are very obvious when kNN search is carried out on obliquely distributed big data on the hash buckets.

Description

technical field [0001] The invention belongs to the field of data analysis, and relates to a k-nearest-neighbor similar query method based on multi-layer local sensitive hash. Background technique [0002] kNN search is a commonly used operation in data analysis. Its purpose is to find the k records closest to the query point (that is, the most similar) from the data set. If you want to find the exact kNN result for a given query point, you have to traverse the entire dataset, calculate the distance of each point in the dataset to the query point, and then find the k closest points to the query point, which requires searching the entire dataset. If kNN search is performed on high-dimensional large-scale data sets, the cost of obtaining accurate kNN results is even greater. If it is necessary to feed back the query results to the user in real time, it is obviously not advisable to perform an accurate kNN query. The approximate kNN search technology is proposed to speed up th...

AI Technical Summary

Problems solved by technology

[0015] Aiming at the problem of uneven size of traditional LSH buckets, the present invention provides a multi-layer Locality-Sensitive Hashing (Locality-Sensitive Hashing) method that supports k Nearest Neighbors (kNN) approximate query, a multi-layer Locality-Sensitive Hashing Hash (LayerLSH) structure and an approximate kNN query method based on this structure, it achieves the effect of adaptively adjusting the size of the buckets by re-dividing the existing hash buckets or merging the existing hash buckets, so that it can effectively Reduce the search cost and improve the accuracy when processing kNN queries with skewed distribution data

Images