apache / apache/lucene

Optimize vector functions by precomputing magnitudes [LUCENE-10191]

Open
#11,228 6 comments 0 reactions 0 assignees View on GitHub
legacy-jira-priority:Minor type:enhancement
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.