Non-Metric Locality-Sensitive Hashing

Yadong Mu, Shuicheng Yan

Locality-Sensitive Hashing (LSH) is a cornerstone of efficient approximate nearest neighbor search. However, traditional LSH families are restricted to metric distances that satisfy the triangle inequality. This paper presents a novel LSH framework for non-metric distances—such as KL divergence and Chamfer distance—by embedding data into an indefinite reproducing kernel Kreĭn space. By preserving the structural information contained in negative eigenvalues, the proposed method significantly improves retrieval accuracy for complex perceptual similarities.

The Challenge of Non-Metric Similarity

Approximate nearest-neighbor (ANN) search is essential for scaling machine learning tasks. While LSH is a popular solution, it typically requires distances to be metrics (e.g., Euclidean or Cosine). In many real-world scenarios, human perceptual similarity is inherently non-metric.

Conceptual illustration of non-metric similarity violations.

As shown in Figure 1, a centaur may be perceived as similar to both a man and a horse, yet the man and horse are dissimilar. This violation of the triangle inequality makes standard LSH ineffective. Common non-metric measures like Kullback-Leibler (KL) divergence or Itakura-Saito divergence often result in indefinite kernels—matrices with both positive and negative eigenvalues.

Leveraging Indefinite Kernels in Kreĭn Spaces

Standard kernelized LSH methods assume a positive semi-definite (PSD) kernel, operating within a Hilbert space. When faced with indefinite kernels, these methods often discard negative eigenvalues as noise. However, these components often carry vital structural information.

Eigenvalue distribution of a non-metric kernel showing significant negative components.

Figure 3 illustrates that negative eigenvalues are not merely noise but represent a substantial portion of the kernel's spectrum. To capture this, the authors utilize reproducing kernel Kreĭn spaces (RKKS). A Kreĭn space is a vector space with an indefinite inner product, decomposable into two Hilbert spaces: $\mathcal{K}_+$ (positive-definite) and $\mathcal{K}_-$ (negative-definite).

The Non-Metric LSH Algorithm

The proposed algorithm follows a two-step process:

  1. Hilbert Space Projection: The indefinite kernel $K$ is decomposed into $K_+$ and $K_-$. Using $p$-stable distributions (specifically Gaussian), the data is projected into these respective Hilbert spaces, preserving $\ell^2$ distances within each.
  2. Kreĭn Space Hashing: The true distance in the Kreĭn space is derived from the difference between the distances in $\mathcal{K}_+$ and $\mathcal{K}_-$. The authors use an algebraic approximation to combine these projections into binary hash bits that reflect the Kreĭn distance.

For out-of-sample queries, a least-squares optimization estimates the query's projection coefficients, allowing new data to be hashed into the existing structure.

Experimental Results

The method was evaluated on four datasets (InternetAds, CIFAR-10, Local-Patch, and USPS-Digit) using various non-metric distances. The primary metric, Good Neighbor Ratio (GNR), measured the success of retrieving the top-5% nearest neighbors.

The results consistently showed that the Kreĭn space approach outperformed baselines that ignored negative eigenvalues. By integrating information from both the positive and negative spectral components, the algorithm achieved significantly higher retrieval accuracy, proving that the "negative" part of the kernel is essential for representing non-metric similarities accurately.

Summary updated

Abstract

Non-metric distances are often more reasonable compared with metric ones in terms of consistency with human perceptions. However, existing locality-sensitive hashing (LSH) algorithms can only support data which are gauged with metrics. In this paper we propose a novel locality-sensitive hashing algorithm targeting such non-metric data. Data in original feature space are embedded into an implicit reproducing kernel Kreĭn space and then hashed to obtain binary bits. Here we utilize the norm-keeping property of p-stable functions to ensure that two data's collision probability reflects their non-metric distance in original feature space. We investigate various concrete examples to validate the proposed algorithm. Extensive empirical evaluations well illustrate its effectiveness in terms of accuracy and retrieval speedup.
BibTeX
@inproceedings{mu2010non,
  author = {Yadong Mu and Shuicheng Yan},
  title = {{Non-Metric Locality-Sensitive Hashing}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2010},
  doi = {10.1609/aaai.v24i1.7683},
}
Figure