Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Manhattan distance #3079

Merged
merged 9 commits into from
Dec 2, 2023
Merged

Manhattan distance #3079

merged 9 commits into from
Dec 2, 2023

Conversation

kaancfidan
Copy link
Contributor

@kaancfidan kaancfidan commented Nov 22, 2023

Depends on qdrant/quantization#21.

This pull request adds Manhattan (L1, taxicab) as a 4th distance type (related to #3052). I am aware that this is an ambitious pull request as a first contribution, but I need the functionality and I think it has a justified place in the product.

The related issue mentions generalized Lp, but I thought it did not make much sense to try to implement AVX/SSE/Neon versions for it.

I have tried to follow the Euclid distance implementation as close as I could and I have copied the tests related to Euclid distance and converted them to Manhattan distance tests. I have also created an OpenAPI integration test for it.

I have implemented all AVX, SSE and Neon optimized similarity functions, they are all tested on proper hardware.

This pull request depends on the changes on the matching pull request at qdrant/quantization repo.

Once the branch at qdrant/quantization is merged, its dependency should be switched back to its usual form.

All Submissions:

  • Contributions should target the dev branch. Did you create your branch from dev?
  • Have you followed the guidelines in our Contributing document?
  • Have you checked to ensure there aren't other open Pull Requests for the same update/change?

New Feature Submissions:

  1. Does your submission pass tests?
  2. Have you formatted your code locally using cargo +nightly fmt --all command prior to submission?
  3. Have you checked your code using cargo clippy --all --all-features command?

Changes to Core Features:

  • Have you added an explanation of what your changes do and why you'd like us to include them?
  • Have you written new tests for your core changes, as applicable?
  • Have you successfully ran tests with your changes locally?

lib/segment/Cargo.toml Outdated Show resolved Hide resolved
@kaancfidan kaancfidan marked this pull request as draft November 22, 2023 21:45
@kaancfidan kaancfidan marked this pull request as ready for review November 23, 2023 22:48
@generall generall merged commit c7402a4 into qdrant:dev Dec 2, 2023
17 checks passed
@kaancfidan kaancfidan deleted the manhattan-distance branch December 2, 2023 20:41
joein pushed a commit that referenced this pull request Dec 6, 2023
* implemented Manhattan distance

* updated quantization dependency

* fixed negative distances and doc consistency

* fixed neon implementation

* updated quantization dependency

* updated quantization dependency

* removed redundant copy operation

* updated quantization dependency

* Change back to upstream quantization dependency

---------

Co-authored-by: timvisee <tim@visee.me>
generall pushed a commit that referenced this pull request Dec 6, 2023
* implemented Manhattan distance

* updated quantization dependency

* fixed negative distances and doc consistency

* fixed neon implementation

* updated quantization dependency

* updated quantization dependency

* removed redundant copy operation

* updated quantization dependency

* Change back to upstream quantization dependency

---------

Co-authored-by: timvisee <tim@visee.me>
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.

3 participants