Skip to content

Acorn1#5369

Merged
abdelr merged 23 commits intostable/v1.27from
ACORN1
Oct 15, 2024
Merged

Acorn1#5369
abdelr merged 23 commits intostable/v1.27from
ACORN1

Conversation

@abdelr
Copy link
Copy Markdown
Contributor

@abdelr abdelr commented Jul 16, 2024

What's being changed:

This PR introduces an ACORN1 like search.
Important features taken from ACORN are:

  1. We totally ignore vectors not passing the filters to speed up search, since we do not calculate distance to them.
  2. We use a multi hop approach to calculate neighbourhood of candidates to improve graph connectivity.

What we do not do from ACORN:

  1. We do not require retraining.
  2. We use random seeding for the entry points during search to speed up convergence to the filtered zone in the case of negatively correlated filters.

What to expect from the implementation:

  1. No state on disk must be changed to support ACORN. You can simply upgrade from 1.26 to 1.27 and benefit from ACORN.
  2. You don’t need any more resources than before, the vector index is the exact same as before.
  3. Since it’s only a query time algorithm change, you can opt in or out at any moment.
  4. For high recall settings we have seen almost 10x performance improvements for filtered queries for those that were very slow before. Still, you might expect 2 to 4x across most queries.
  5. We have seen some small recall degradation under lab conditions. This might be negligible in real life settings though.

Finally, we add some tests with the super beir data. In the chart, Main stands for the old logic, while ACORN stands for the new logic, and the suffix indicate whether we use positive or negative correlation for the filter.
output (2)

Review checklist

  • Documentation has been updated, if necessary. Link to changed documentation:
  • Chaos pipeline run or not necessary. Link to pipeline:
  • All new code is covered by tests where it is reasonable.
  • Performance tests have been run or not necessary.

@abdelr abdelr self-assigned this Jul 16, 2024
@abdelr abdelr requested a review from trengrj July 16, 2024 15:47
@sonarqubecloud
Copy link
Copy Markdown

Quality Gate Failed Quality Gate failed

Failed conditions
14.8% Duplication on New Code (required ≤ 3%)

See analysis details on SonarCloud

Comment thread test/acceptance/schema/get_schema_without_client_test.go Outdated
@abdelr abdelr force-pushed the ACORN1 branch 3 times, most recently from 3f628f6 to 9ff18a2 Compare October 9, 2024 14:49
Comment thread adapters/repos/db/vector/hnsw/search.go
Comment thread adapters/repos/db/vector/hnsw/search.go Outdated
Comment thread adapters/repos/db/vector/hnsw/search.go
Comment thread adapters/repos/db/vector/hnsw/search.go Outdated
Comment thread adapters/repos/db/vector/hnsw/search.go Outdated
Comment thread adapters/repos/db/vector/hnsw/search.go Outdated
Comment thread adapters/repos/db/vector/hnsw/search.go Outdated
Comment thread adapters/repos/db/vector/hnsw/search.go Outdated
Comment thread adapters/repos/db/vector/hnsw/search.go
Comment thread adapters/repos/db/vector/hnsw/search.go Outdated
Comment thread adapters/repos/db/vector/hnsw/search.go Outdated
Comment thread adapters/repos/db/vector/hnsw/search.go
Comment thread adapters/repos/db/vector/hnsw/search.go Outdated
Comment thread adapters/repos/db/vector/hnsw/search.go Outdated
@trengrj trengrj changed the base branch from main to stable/v1.27 October 14, 2024 10:06
@sonarqubecloud
Copy link
Copy Markdown

Quality Gate Failed Quality Gate failed

Failed conditions
12.2% Duplication on New Code (required ≤ 3%)

See analysis details on SonarCloud

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

4 participants