High-dimensional similarity searches using query driven dynamic quantization and distributed indexing.

Area of Science:

• Data Mining
• Machine Learning
• Computer Science

Background:

• Nearest neighbor (NN) queries are crucial for data exploration and mining.
• Traditional distance functions struggle with high-dimensional data, diminishing the effectiveness of NN searches.
• 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 similarity searches in high-dimensional datasets.
• To develop a distributed algorithm for efficient QED computation.

Main Methods:

• Implemented a query-dependent equi-depth (QED) quantization technique.
• Generated localized similarity scores for a fraction of points and applied penalties to others.
• Developed a distributed indexing and query algorithm for QED computation.

Main Results:

• QED significantly improves the quality of the distance metric in high-dimensional spaces.
• Achieved up to one order of magnitude faster query performance compared to traditional methods.
• Demonstrated linear or better scalability with increasing dimensions and compute nodes.

Conclusions:

• QED offers a superior approach to high-dimensional similarity searches, enhancing both accuracy and speed.
• The proposed method effectively filters irrelevant data, improving overall search efficiency.
• QED provides a scalable solution for nearest neighbor queries in large, high-dimensional datasets.