Journal Article

A robust method based on locality sensitive hashing for K-nearest neighbors searching

Zhang, Sulan, Wu, Quanwang, Cheng, Dongdong, Huang, Jinlong

2024

Overview

K-nearest neighbors searching (KNNS) is to find K -nearest neighbors for query points. It is a primary problem in clustering analysis, classification, outlier detection and pattern recognition, and has been widely used in various applications. The exact searching algorithms, like KD-tree, M-tree, are not suitable for high-dimensional data. Approximate KNNS algorithms for high-dimensional data based on locality sensitive hashing (LSH) is becoming popular. However, the existing searching strategies are sensitive to the parameters of constructing LSH index. To solve this problem, a robust strategy for KNNS, called Robust-LSH, is proposed. It makes full use of points that frequently appear together with the query points to improve the diversity of candidates, so that it can use fewer hash tables to obtain more valuable candidates for KNNS. We do experiments on synthetic and real data. The results show that in terms of searching accuracy and running time, Robust-LSH has better performance than the p-stable LSH, RLSH and KD-tree algorithms.

• Publisher: Springer US
• Subject: Communications Engineering / Computer Communication Networks / Electrical Engineering / Engineering / IT in Business / Networks