A Method for Fast Adapting Similarity Searches Based on Variance Aware Quantization

SUMMARY

• With the explosive growth of high-dimensional data, approximate methods emerge as promising solutions for searching for similar data pairs.
• Quantization methods have gained prominence due to their low storage costs and fast query responses.  These methods decompose data dimensions into subspaces and their performance critically depends on maintaining effective dictionaries per subspace.  However, the lack of a solution to improve the runtime performance without sacrificing accuracy or limiting the possible configurations hinders the wide adoption of quantization methods.
• The faculty inventor introduces a new data-driven quantization method, Variance-Aware Quantization (VAQ), to automatically encode data vectors by intelligently adapting the dictionary sizes to non-uniform subspaces based on their relative importance (the amount of variance explained by each subspace).
• Through an evaluation on over one hundred datasets, VAQ outperforms the state-of-the-art quantization and cans-based methods.

FIGURE

ADVANTAGES

ADVANTAGES

• High accuracy and sustainability
• Accelerated query performance
• Competitive runtime performance

APPLICATIONS

• Image databases
• Comparisons in document collections
• Time-series databases
• Genome databases

PUBLICATIONS

• J. Paparrizos, I. Edian, C. Liu, A. J. Elmore and M. J. Franklin, "Fast Adaptive Similarity Search through Variance-Aware Quantization," 2022 IEEE 38th International Conference on Data Engineering (ICDE), 2022, pp. 2969-2983, doi: 10.1109/ICDE53745.2022.00268.

Jan 20, 2023

Licensing,Co-development

Patent Pending

Proof of concept

Michael Franklin