Distributed query-aware quantization for high-dimensional similarity searches.

Area of Science:

• Data Mining
• Machine Learning
• Information Retrieval

Background:

• Similarity is crucial for data exploration and nearest neighbor (NN) queries.
• Traditional distance functions struggle in high-dimensional spaces due to dominating dissimilar dimensions.
• Existing localized similarity functions use query-agnostic quantization, limiting accuracy.

Purpose of the Study:

• To propose a novel Query dependent Equi-Depth (QED) on-the-fly quantization method.
• To enhance the accuracy and efficiency of high-dimensional similarity searches.
• To introduce a distributed algorithm for efficient QED computation.

Main Methods:

• Developed a query-dependent, on-the-fly quantization technique (QED).
• Quantization is applied per dimension at query time.
• Localized scores are computed for a fraction of points, with a penalty for others.

Main Results:

• QED improves the quality of the distance metric in high-dimensional data.
• Achieved significant query time performance improvements, up to an order of magnitude faster than baseline methods.
• Demonstrated enhanced classification accuracy on high-dimensional datasets.

Conclusions:

• QED offers a superior approach to high-dimensional similarity searching compared to traditional and existing localized methods.
• The proposed distributed algorithm efficiently computes QED, enabling practical application.
• QED effectively filters irrelevant data, leading to substantial performance gains.