Asymmetric distance estimation with sketches for similarity search in high-dimensional spaces

Wei Dong, Moses Charikar, Kai LiSIGIR 2008 · OpenReview

Abstract

Efficient similarity search in high-dimensional spaces is a cornerstone of modern content-based retrieval. While sketches provide a compact way to approximate distances, reducing their size without sacrificing accuracy remains a significant challenge. This paper introduces a novel asymmetric distance estimation (ADE) technique that leverages the full precision of the query vector at search time. By comparing a raw query against compact data sketches, ADE achieves a 10% to 40% reduction in storage requirements for the same level of search quality. We also present a new $L_2$ sketch algorithm based on a spatial striping technique.

Introduction

In fields such as image retrieval and audio analysis, objects are represented as high-dimensional feature vectors. Finding the "nearest neighbors" to a query in these spaces is computationally expensive—a phenomenon known as the "curse of dimensionality." To accelerate this process, researchers utilize sketches: compact bit-vectors that approximate the original data.

The standard "filtering" workflow involves scanning these tiny sketches to identify a small set of candidates, which are then ranked using the original, high-precision feature vectors. However, practitioners face a trade-off: small sketches are fast but inaccurate (low recall), while large sketches consume excessive memory. This research explores how to extract higher accuracy from small sketches without increasing storage costs.

Methodology: Asymmetric Distance Estimation

The core innovation presented is the transition from symmetric to asymmetric estimation.

Symmetric vs. Asymmetric Estimation

  • Symmetric (Standard): The query is converted into a sketch, and the distance is estimated by comparing two sketches (e.g., using Hamming distance). This process discards the precise position of the query point.
  • Asymmetric (Proposed): The query is kept in its original feature space and compared directly to the data sketches. Since the query is already in memory at runtime, using its full precision is "free" in terms of storage.

The $L_2$ Striping Sketch

The authors introduce a new sketch for Euclidean ($L_2$) distance based on a "striping" technique. Space is randomly partitioned into interleaving gray and white stripes. A point is assigned a '0' or '1' bit based on the stripe it occupies.

The L2 partitioning scheme (a) uses stripes to generate sketch bits, and (b) shows the expected sketch distance relative to L2 distance.

In the asymmetric estimator, the distance from the query point to the nearest stripe boundary ($\delta$) serves as a weight. If a query is centered in a stripe, a bit mismatch with a data point is a strong signal of distance; if it is near the edge, the signal is weaker. This refined logic provides a much tighter lower bound on the actual distance than simple bit-counting.

Evaluation and Results

The researchers evaluated their methods on two large-scale, real-world datasets: 4.5 million SIFT feature vectors (Image) and 2.5 million MFCC feature vectors (Audio).

Performance and Accuracy

The asymmetric approach consistently outperformed symmetric methods across all tested distance measures ($L_2$, Cosine, and $L_1$). To achieve the same search quality (recall), asymmetric estimators reduced the required sketch size by 10% to 40%.

Comparison of mean squared error for symmetric and asymmetric estimators across different cosine similarity values.

As illustrated in the error analysis for cosine similarity, the asymmetric estimator significantly reduces the mean squared error compared to the symmetric baseline. This improvement is particularly pronounced in the high-similarity regions most relevant to nearest-neighbor search.

Conclusion

Asymmetric distance estimation effectively utilizes available query-side information to boost search accuracy. By treating the query as a precise point and the data as regions defined by sketch bits, it eliminates approximately half of the uncertainty inherent in traditional sketching. While it introduces some computational overhead, the significant gains in storage efficiency and search quality make it a powerful tool for high-dimensional similarity search.

This summary is based on the paper "Asymmetric distance estimation with sketches for similarity search in high-dimensional spaces," presented at SIGIR 2008.

Summary updated

Abstract

Efficient similarity search in high-dimensional spaces is important to content-based retrieval systems. Recent studies have shown that sketches can effectively approximate L1 distance in high-dimensional spaces, and that filtering with sketches can speed up similarity search by an order of magnitude. It is a challenge to further reduce the size of sketches, which are already compact, without compromising accuracy of distance estimation. This paper presents an efficient sketch algorithm for similarity search with L2 distances and a novel asymmetric distance estimation technique. Our new asymmetric estimator takes advantage of the original feature vector of the query to boost the distance estimation accuracy. We also apply this asymmetric method to existing sketches for cosine similarity and L1 distance. Evaluations with datasets extracted from images and telephone records show that our L2 sketch outperforms existing methods, and the asymmetric estimators consistently improve the accuracy of different sketch methods. To achieve the same search quality, asymmetric estimators can reduce the sketch size by 10% to 40%.
BibTeX
@inproceedings{dong2008asymmetric,
  author = {Wei Dong and Moses Charikar and Kai Li},
  title = {{Asymmetric distance estimation with sketches for similarity search in high-dimensional spaces}},
  booktitle = {International ACM SIGIR Conference on Research and Development in Information Retrieval},
  year = {2008},
  url = {https://openreview.net/forum?id=nD2Y3G2Bvxf},
}
Figure