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.

Sign up for GitHub

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

Jump to bottom

[FEA] Pre-filtered brute-force KNN #1969

Closed
cjnolet opened this issue Nov 7, 2023 · 0 comments
Closed

[FEA] Pre-filtered brute-force KNN #1969

cjnolet opened this issue Nov 7, 2023 · 0 comments
Assignees
@rhdong
Labels
FAISS feature request New feature or request Milvus REDIS Vector Search

Comments

@cjnolet
Copy link
Member

cjnolet commented Nov 7, 2023 •
edited
Loading

This is an important building block and can be implemented easily once we have a masked matmul primitive available. We can likely use the SDDMM primitive from cuSparse for the dot-product based distances and then eventually build our own for the non-dot-product based.

cc @benfred
@cjnolet cjnolet added feature request New feature or request Vector Search labels Nov 7, 2023
@cjnolet cjnolet moved this from Todo to In Progress in VS/ML/DM Primitives Release Board Jan 12, 2024
@rhdong rhdong mentioned this issue Jan 23, 2024
Merged
copy-pr-bot bot pushed a commit that referenced this issue Jan 23, 2024
@rhdong
[FEA] Add support for bitmap_view & the API of bitmap_to_csr
165b278 
- This PR is one part of the Feature of [FEA] Pre-filtered brute-force KNN #1969

Authors:
  - James Rong (https://github.com/rhdong)

Approvers:
  - Ben Frederickson (https://github.com/benfred)
  - Micka (https://github.com/lowener)
  - Corey J. Nolet (https://github.com/cjnolet)
@rhdong rhdong mentioned this issue Jan 31, 2024
Merged
copy-pr-bot bot pushed a commit that referenced this issue Jan 31, 2024
@rhdong
[FEA] Add support for select_k on CSR matrix
5071971 
- This PR is one part of the feature of #1969
- Add the API of 'select_k' accepting CSR as input
- Add the API of 'segmented_copy'

Authors:
  - James Rong (https://github.com/rhdong)

Approvers:
  - Ben Frederickson (https://github.com/benfred)
  - Micka (https://github.com/lowener)
  - Corey J. Nolet (https://github.com/cjnolet)
rapids-bot bot pushed a commit that referenced this issue Mar 21, 2024
@rhdong
[FEA] Add support for bitmap_view & the API of bitmap_to_csr (#2109)
fd91efb 
- This PR is one part of the feature of #1969

Authors:
  - James Rong (https://github.com/rhdong)

Approvers:
  - Ben Frederickson (https://github.com/benfred)
  - Micka (https://github.com/lowener)
  - Corey J. Nolet (https://github.com/cjnolet)

Authors:
  - rhdong (https://github.com/rhdong)

Approvers:
  - Corey J. Nolet (https://github.com/cjnolet)
  - Micka (https://github.com/lowener)

URL: #2109
rapids-bot bot pushed a commit that referenced this issue Apr 8, 2024
@rhdong
[FEA] Add support for select_k on CSR matrix (#2140)
4a20d03 
- This PR is one part of the feature of #1969
- Add the API of 'select_k' accepting CSR as input
Authors:
  - James Rong (https://github.com/rhdong)

Approvers:
  - Ben Frederickson (https://github.com/benfred)
  - Micka (https://github.com/lowener)
  - Corey J. Nolet (https://github.com/cjnolet)

Authors:
  - rhdong (https://github.com/rhdong)

Approvers:
  - Artem M. Chirkin (https://github.com/achirkin)
  - Corey J. Nolet (https://github.com/cjnolet)

URL: #2140
@rhdong rhdong mentioned this issue May 7, 2024
Merged
copy-pr-bot bot pushed a commit that referenced this issue May 7, 2024
@rhdong
[FEA] support of prefiltered brute force based on cuSparseSDDMM
d85fcf0 
- This PR is one part of the feature of #1969
- Add the API of 'search_with_filtering' for brute force.
Authors:
  - James Rong (https://github.com/rhdong)
rapids-bot bot pushed a commit that referenced this issue May 24, 2024
@rhdong
[FEA] support of prefiltered brute force (#2294)
5f0dfed 
- This PR is one part of the feature of #1969
- Add the API of 'search_with_filtering' for brute force.
Authors:
  - James Rong (https://github.com/rhdong)

```shell
***WARNING*** CPU scaling is enabled, the benchmark real time measurements may be noisy and will incur extra overhead.
-----------------------------------------------------------------------------------------------------
Benchmark                                                           Time             CPU   Iterations
-----------------------------------------------------------------------------------------------------
KNN/float/int64_t/brute_force_filter_knn/0/0/0/manual_time       33.1 ms         69.9 ms           21 1000000#128#1000#255#0#InnerProduct#NO_COPY#SEARCH
KNN/float/int64_t/brute_force_filter_knn/1/0/0/manual_time       38.0 ms         74.8 ms           18 1000000#128#1000#255#0#L2Expanded#NO_COPY#SEARCH
KNN/float/int64_t/brute_force_filter_knn/2/0/0/manual_time       41.7 ms         78.5 ms           17 1000000#128#1000#255#0.8#InnerProduct#NO_COPY#SEARCH
KNN/float/int64_t/brute_force_filter_knn/3/0/0/manual_time       57.5 ms         94.3 ms           12 1000000#128#1000#255#0.8#L2Expanded#NO_COPY#SEARCH
KNN/float/int64_t/brute_force_filter_knn/4/0/0/manual_time       19.7 ms         56.4 ms           35 1000000#128#1000#255#0.9#InnerProduct#NO_COPY#SEARCH
KNN/float/int64_t/brute_force_filter_knn/5/0/0/manual_time       26.1 ms         62.8 ms           27 1000000#128#1000#255#0.9#L2Expanded#NO_COPY#SEARCH```

Authors:
  - rhdong (https://github.com/rhdong)
  - Artem M. Chirkin (https://github.com/achirkin)
  - Corey J. Nolet (https://github.com/cjnolet)

Approvers:
  - Robert Maynard (https://github.com/robertmaynard)
  - Corey J. Nolet (https://github.com/cjnolet)
  - Divye Gala (https://github.com/divyegala)

URL: #2294
@cjnolet cjnolet closed this as completed Jun 3, 2024
@github-project-automation github-project-automation bot moved this from In Progress to Done in VS/ML/DM Primitives Release Board Jun 3, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@rhdong rhdong

Labels
FAISS feature request New feature or request Milvus REDIS Vector Search
Projects
VS/ML/DM Primitives Release Board
Status: Done
Milestone
No milestone
Development

No branches or pull requests
2 participants
@cjnolet @rhdong