A Novel Method for Similarity Search in High-Dimensional Spaces

What is it about?

Locality-Sensitive Hashing (LSH) and its variants are the well-known indexing schemes for the Nearest Neighbor Search (NNS) problem in high-dimensional Euclidean space. In this paper, we introduce a novel concept of query-aware bucket partition, which uses a given query as the anchor for bucket partition. With the query-aware bucket partition, we propose a novel provable Query-Aware LSH (QALSH) scheme for c-NNS over external memory, which works with an approximation ratio c > 1. Extensive experiments show that QALSH outperforms two state-of-the-art LSH schemes C2LSH and LSB-Forest, especially in high-dimensional spaces.

Featured Image

Photo by Markus Winkler on Unsplash

Photo by Markus Winkler on Unsplash

Why is it important?

Vanilla LSH functions are constructed in a query-oblivious manner in the sense that buckets are partitioned before any query arrives. However, objects closer to a query may be partitioned into different buckets, which leads to a high search error. Moreover, due to the use of query-oblivious bucket partition, the state-of-the-art LSH schemes for external memory, namely C2LSH and LSB-Forest, only work with an integer c ≥ 2. In order to fix those problems, we design a novel query-aware LSH function based on the query position. We also simply the function as a random projection coupled with the query-aware bucket partition, which removes the random shift required by traditional query-oblivious LSH functions. Notably, query-aware bucket partition can be easily implemented so that query performance is guaranteed.

Perspectives