SymmetricalDataSecurity: ScaNN: Efficient Vector Similarity Search

Wednesday, July 29, 2020

ScaNN: Efficient Vector Similarity Search

Posted by Philip Sun, Software Engineer, Google ResearchICML 2020Accelerating Large-Scale Inference with Anisotropic Vector Quantization,”vector similarity search libraryann-benchmarks.comThe Importance of Vector Similarity Search

The two-tower neural network model, illustrated above, is a specific type of embedding-based search where queries and database items are mapped to the embedding space by two respective neural networks. In this example the model responds to natural-language queries for a hypothetical literary database.

nearest neighbor searchinner productmaximum inner-product searchA New Quantization Approach for MIPSSeveral state-of-the-art solutionslearned quantizationcodebookxx̃higherx1x2c1c2x_ix̃_iqx̃_iqx_ix̃_iqx_iqx_iqx̃₁greaterqx̃2qx1lessqx2x1c1x2c2

The goal is to quantize each x_i to x̃_i = c₁ or x̃_i = c₂. Traditional quantization (left) results in the incorrect ordering of x₁ and x₂ for this query. Even though our approach (right) chooses centers farther away from the data points, this in fact leads to lower inner product error and higher accuracy.

c1x1c2c1x1x1c2x2anisotropic vector quantization

In the above diagrams, ellipses denote contours of equal loss. In anisotropic vector quantization, error parallel to the original data point x is penalized more.

Anisotropic Vector Quantization in ScaNNkglove-100-angular benchmarkann-benchmarks.com^*

Recall@k is a commonly used metric for nearest neighbor search accuracy, which measures the proportion of the true nearest k neighbors that are present in an algorithm’s returned k neighbors. ScaNN (upper purple line) consistently achieves superior performance across various points of the speed-accuracy trade-off.

GitHubConclusionstate-of-the-art performanceAcknowledgementsThis post reflects the work of the entire ScaNN team: David Simcha, Erik Lindgren, Felix Chern, Nathan Cordeiro, Ruiqi Guo, Sanjiv Kumar, and Zonglin Li. We’d also like to thank Dan Holtmann-Rice, Dave Dopson, and Felix Yu.
* ScaNN performs similarly well on the other datasets of ann-benchmarks.com, but the website currently shows outdated, lower numbers. See this pull request for more representative performance figures on other datasets. ↩

from Hacker News https://ift.tt/2P5HNku

SymmetricalDataSecurity

Wednesday, July 29, 2020

ScaNN: Efficient Vector Similarity Search

No comments:

Post a Comment

Blog Archive

Search This Blog

Total Pageviews