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.
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%.
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