Optimize vector functions by precomputing magnitudes [LUCENE-10191]
- Dominant language
- Java
- Stars
- 3.6k
- Forks
- 1.4k
- Avg merge
- 2d 11h
- Merged PRs (30d)
- 88
Description
Both euclidean distance (L2 norm) and cosine similarity can be expressed in terms of dot product and vector magnitudes:
- l2_norm(a, b) = ||a - b|| = sqrt(||a||^2 - 2(a . b) + ||b||^2)
- cosine(a, b) = a . b / ||a|| ||b||
We could compute and store each vector's magnitude upfront while indexing, and compute the query vector's magnitude once per query. Then we'd calculate the distance using our (very optimized) dot product method, plus the precomputed values.
This is an exploratory issue: I haven't tested this out yet, so I'm not sure how much it would help. I would at least expect it to help with cosine similarity – several months ago we tried out similar ideas in Elasticsearch and were able to get a nice boost in cosine performance.
---
Migrated from [LUCENE-10191](https://issues.apache.org/jira/browse/LUCENE-10191) by Julie Tibshirani (@jtibshirani), 1 vote, updated Dec 15 2021
Contributor guide
Research direction
The issue names no files or tests. Start by locating the vector indexing and distance or similarity entry points, then benchmark the existing dot-product calculations against precomputed magnitudes. Done means confirming a measurable improvement, especially for cosine similarity, while preserving the expected distance and similarity results.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- java
- Domain
- performance, search
- Issue type
- Refactor
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 30/100