web analytics

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

Published:
Lead Inventor: Michael Franklin
Print or Save to PDF

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

Comparison of quantization methods across three large-scale datasets. For the same budget, hardware-accelerated methods (i.e., Bolt and PQFS) may sacrifice accuracy (vs. PQ and OPQ) to accelerate the query execution. In contrast, our method, VAQ, outperforms Bolt and PQFS in terms of runtime while significantly improving accuracy compared to PQ and OPQ.

 

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.