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

[FEA] Add bitset_filter for CAGRA indices removal #1837

Merged
merged 22 commits into from
Oct 3, 2023

Conversation

lowener
Copy link
Contributor

@lowener lowener commented Sep 22, 2023

Closes #1600.
To be merged after #1803 and #1811
This PR adds bitset_filter to filter an index with a bitset.

@copy-pr-bot
Copy link

copy-pr-bot bot commented Sep 22, 2023

This pull request requires additional validation before any workflows can run on NVIDIA's runners.

Pull request vetters can view their responsibilities here.

Contributors can view more details about this message here.

@lowener lowener added the 2 - In Progress Currenty a work in progress label Sep 22, 2023
@lowener
Copy link
Contributor Author

lowener commented Sep 22, 2023

Current benchmark performance on my local machine (with the corresponding removed_ratio of 2%, 4%, 8%, ..):

AnnCagra/float/uint32_t/21/manual_time       4.09 ms         4.13 ms          171 block_size=256 dataset (GiB)=0.953674 degree=64 graph (GiB)=0.476837 iterations=36 itopk_size=64 k=32 n_cols=128 n_queries=1000 n_rows=2M removed_ratio=0 search_width=2
AnnCagra/float/uint32_t/22/manual_time       4.10 ms         4.14 ms          171 block_size=256 dataset (GiB)=0.953674 degree=64 graph (GiB)=0.476837 iterations=36 itopk_size=64 k=32 n_cols=128 n_queries=1000 n_rows=2M removed_ratio=0.02 search_width=2
AnnCagra/float/uint32_t/23/manual_time       4.10 ms         4.14 ms          171 block_size=256 dataset (GiB)=0.953674 degree=64 graph (GiB)=0.476837 iterations=36 itopk_size=64 k=32 n_cols=128 n_queries=1000 n_rows=2M removed_ratio=0.04 search_width=2
AnnCagra/float/uint32_t/24/manual_time       4.11 ms         4.15 ms          170 block_size=256 dataset (GiB)=0.953674 degree=64 graph (GiB)=0.476837 iterations=36 itopk_size=64 k=32 n_cols=128 n_queries=1000 n_rows=2M removed_ratio=0.08 search_width=2
AnnCagra/float/uint32_t/25/manual_time       4.10 ms         4.14 ms          171 block_size=256 dataset (GiB)=0.953674 degree=64 graph (GiB)=0.476837 iterations=36 itopk_size=64 k=32 n_cols=128 n_queries=1000 n_rows=2M removed_ratio=0.16 search_width=2
AnnCagra/float/uint32_t/26/manual_time       4.09 ms         4.13 ms          171 block_size=256 dataset (GiB)=0.953674 degree=64 graph (GiB)=0.476837 iterations=36 itopk_size=64 k=32 n_cols=128 n_queries=1000 n_rows=2M removed_ratio=0.32 search_width=2
AnnCagra/float/uint32_t/27/manual_time       4.09 ms         4.13 ms          171 block_size=256 dataset (GiB)=0.953674 degree=64 graph (GiB)=0.476837 iterations=36 itopk_size=64 k=32 n_cols=128 n_queries=1000 n_rows=2M removed_ratio=0.64 search_width=2

@lowener lowener added feature request New feature or request non-breaking Non-breaking change labels Sep 22, 2023
@cjnolet
Copy link
Member

cjnolet commented Sep 26, 2023

/ok to test

1 similar comment
@lowener
Copy link
Contributor Author

lowener commented Sep 26, 2023

/ok to test

@github-actions github-actions bot removed the CMake label Sep 26, 2023
@lowener
Copy link
Contributor Author

lowener commented Sep 26, 2023

/ok to test

@lowener lowener mentioned this pull request Sep 27, 2023
@lowener
Copy link
Contributor Author

lowener commented Sep 28, 2023

/ok to test

@lowener lowener marked this pull request as ready for review September 28, 2023 20:24
@lowener lowener requested a review from a team as a code owner September 28, 2023 20:24
@lowener lowener added 3 - Ready for Review and removed 2 - In Progress Currenty a work in progress labels Sep 28, 2023
@lowener
Copy link
Contributor Author

lowener commented Sep 28, 2023

Latest benchmark results on my local machine. The difference between none_filter and bitset_filter is definitely noticeable now.

AnnCagra/float/uint32_t/21/manual_time       3.72 ms         3.76 ms          188 block_size=256 dataset (GiB)=0.953674 degree=64 graph (GiB)=0.476837 iterations=36 itopk_size=64 k=32 n_cols=128 n_queries=1000 n_rows=2M removed_ratio=0 search_width=2
AnnCagra/float/uint32_t/22/manual_time       6.15 ms         6.19 ms          114 block_size=256 dataset (GiB)=0.953674 degree=64 graph (GiB)=0.476837 iterations=36 itopk_size=64 k=32 n_cols=128 n_queries=1000 n_rows=2M removed_ratio=0.02 search_width=2
AnnCagra/float/uint32_t/23/manual_time       6.17 ms         6.22 ms          113 block_size=256 dataset (GiB)=0.953674 degree=64 graph (GiB)=0.476837 iterations=36 itopk_size=64 k=32 n_cols=128 n_queries=1000 n_rows=2M removed_ratio=0.04 search_width=2
AnnCagra/float/uint32_t/24/manual_time       6.18 ms         6.22 ms          113 block_size=256 dataset (GiB)=0.953674 degree=64 graph (GiB)=0.476837 iterations=36 itopk_size=64 k=32 n_cols=128 n_queries=1000 n_rows=2M removed_ratio=0.08 search_width=2
AnnCagra/float/uint32_t/25/manual_time       6.19 ms         6.23 ms          113 block_size=256 dataset (GiB)=0.953674 degree=64 graph (GiB)=0.476837 iterations=36 itopk_size=64 k=32 n_cols=128 n_queries=1000 n_rows=2M removed_ratio=0.16 search_width=2
AnnCagra/float/uint32_t/26/manual_time       6.20 ms         6.24 ms          113 block_size=256 dataset (GiB)=0.953674 degree=64 graph (GiB)=0.476837 iterations=36 itopk_size=64 k=32 n_cols=128 n_queries=1000 n_rows=2M removed_ratio=0.32 search_width=2
AnnCagra/float/uint32_t/27/manual_time       6.25 ms         6.28 ms          112 block_size=256 dataset (GiB)=0.953674 degree=64 graph (GiB)=0.476837 iterations=36 itopk_size=64 k=32 n_cols=128 n_queries=1000 n_rows=2M removed_ratio=0.64 search_width=2

@lowener lowener changed the title [FEA] Add CAGRA indices removal [FEA] Add bitset_filter for CAGRA indices removal Sep 28, 2023
@lowener
Copy link
Contributor Author

lowener commented Sep 29, 2023

Current result of benchmark of bench-prims on 10M points, batch size 1, 10, 10lk

AnnCagra/float/uint32_t/35/manual_time      0.299 ms        0.340 ms         2343 block_size=256 dataset (GiB)=4.76837 degree=64 graph (GiB)=2.38419 iterations=36 itopk_size=64 k=32 n_cols=128 n_queries=1 n_rows=10M removed_ratio=0 search_width=2
AnnCagra/float/uint32_t/36/manual_time      0.332 ms        0.373 ms         2111 block_size=256 dataset (GiB)=4.76837 degree=64 graph (GiB)=2.38419 iterations=36 itopk_size=64 k=32 n_cols=128 n_queries=1 n_rows=10M removed_ratio=0.02 search_width=2
AnnCagra/float/uint32_t/37/manual_time      0.333 ms        0.375 ms         2100 block_size=256 dataset (GiB)=4.76837 degree=64 graph (GiB)=2.38419 iterations=36 itopk_size=64 k=32 n_cols=128 n_queries=1 n_rows=10M removed_ratio=0.04 search_width=2
AnnCagra/float/uint32_t/38/manual_time      0.339 ms        0.381 ms         2062 block_size=256 dataset (GiB)=4.76837 degree=64 graph (GiB)=2.38419 iterations=36 itopk_size=64 k=32 n_cols=128 n_queries=1 n_rows=10M removed_ratio=0.08 search_width=2
AnnCagra/float/uint32_t/39/manual_time      0.351 ms        0.393 ms         1991 block_size=256 dataset (GiB)=4.76837 degree=64 graph (GiB)=2.38419 iterations=36 itopk_size=64 k=32 n_cols=128 n_queries=1 n_rows=10M removed_ratio=0.16 search_width=2
AnnCagra/float/uint32_t/40/manual_time      0.369 ms        0.411 ms         1895 block_size=256 dataset (GiB)=4.76837 degree=64 graph (GiB)=2.38419 iterations=36 itopk_size=64 k=32 n_cols=128 n_queries=1 n_rows=10M removed_ratio=0.32 search_width=2
AnnCagra/float/uint32_t/41/manual_time      0.382 ms        0.424 ms         1831 block_size=256 dataset (GiB)=4.76837 degree=64 graph (GiB)=2.38419 iterations=36 itopk_size=64 k=32 n_cols=128 n_queries=1 n_rows=10M removed_ratio=0.64 search_width=2
AnnCagra/float/uint32_t/42/manual_time      0.308 ms        0.347 ms         2271 block_size=256 dataset (GiB)=4.76837 degree=64 graph (GiB)=2.38419 iterations=36 itopk_size=64 k=32 n_cols=128 n_queries=10 n_rows=10M removed_ratio=0 search_width=2
AnnCagra/float/uint32_t/43/manual_time      0.342 ms        0.381 ms         2047 block_size=256 dataset (GiB)=4.76837 degree=64 graph (GiB)=2.38419 iterations=36 itopk_size=64 k=32 n_cols=128 n_queries=10 n_rows=10M removed_ratio=0.02 search_width=2
AnnCagra/float/uint32_t/44/manual_time      0.344 ms        0.384 ms         2032 block_size=256 dataset (GiB)=4.76837 degree=64 graph (GiB)=2.38419 iterations=36 itopk_size=64 k=32 n_cols=128 n_queries=10 n_rows=10M removed_ratio=0.04 search_width=2
AnnCagra/float/uint32_t/45/manual_time      0.353 ms        0.392 ms         1982 block_size=256 dataset (GiB)=4.76837 degree=64 graph (GiB)=2.38419 iterations=36 itopk_size=64 k=32 n_cols=128 n_queries=10 n_rows=10M removed_ratio=0.08 search_width=2
AnnCagra/float/uint32_t/46/manual_time      0.360 ms        0.399 ms         1945 block_size=256 dataset (GiB)=4.76837 degree=64 graph (GiB)=2.38419 iterations=36 itopk_size=64 k=32 n_cols=128 n_queries=10 n_rows=10M removed_ratio=0.16 search_width=2
AnnCagra/float/uint32_t/47/manual_time      0.382 ms        0.421 ms         1834 block_size=256 dataset (GiB)=4.76837 degree=64 graph (GiB)=2.38419 iterations=36 itopk_size=64 k=32 n_cols=128 n_queries=10 n_rows=10M removed_ratio=0.32 search_width=2
AnnCagra/float/uint32_t/48/manual_time      0.393 ms        0.433 ms         1779 block_size=256 dataset (GiB)=4.76837 degree=64 graph (GiB)=2.38419 iterations=36 itopk_size=64 k=32 n_cols=128 n_queries=10 n_rows=10M removed_ratio=0.64 search_width=2
AnnCagra/float/uint32_t/49/manual_time       37.4 ms         37.4 ms           19 block_size=256 dataset (GiB)=4.76837 degree=64 graph (GiB)=2.38419 iterations=36 itopk_size=64 k=32 n_cols=128 n_queries=10k n_rows=10M removed_ratio=0 search_width=2
AnnCagra/float/uint32_t/50/manual_time       62.0 ms         62.0 ms           11 block_size=256 dataset (GiB)=4.76837 degree=64 graph (GiB)=2.38419 iterations=36 itopk_size=64 k=32 n_cols=128 n_queries=10k n_rows=10M removed_ratio=0.02 search_width=2
AnnCagra/float/uint32_t/51/manual_time       62.1 ms         62.1 ms           11 block_size=256 dataset (GiB)=4.76837 degree=64 graph (GiB)=2.38419 iterations=36 itopk_size=64 k=32 n_cols=128 n_queries=10k n_rows=10M removed_ratio=0.04 search_width=2
AnnCagra/float/uint32_t/52/manual_time       62.3 ms         62.3 ms           11 block_size=256 dataset (GiB)=4.76837 degree=64 graph (GiB)=2.38419 iterations=36 itopk_size=64 k=32 n_cols=128 n_queries=10k n_rows=10M removed_ratio=0.08 search_width=2
AnnCagra/float/uint32_t/53/manual_time       62.8 ms         62.4 ms           11 block_size=256 dataset (GiB)=4.76837 degree=64 graph (GiB)=2.38419 iterations=36 itopk_size=64 k=32 n_cols=128 n_queries=10k n_rows=10M removed_ratio=0.16 search_width=2
AnnCagra/float/uint32_t/54/manual_time       62.4 ms         62.4 ms           11 block_size=256 dataset (GiB)=4.76837 degree=64 graph (GiB)=2.38419 iterations=36 itopk_size=64 k=32 n_cols=128 n_queries=10k n_rows=10M removed_ratio=0.32 search_width=2
AnnCagra/float/uint32_t/55/manual_time       62.9 ms         62.9 ms           11 block_size=256 dataset (GiB)=4.76837 degree=64 graph (GiB)=2.38419 iterations=36 itopk_size=64 k=32 n_cols=128 n_queries=10k n_rows=10M removed_ratio=0.64 search_width=2

@lowener
Copy link
Contributor Author

lowener commented Sep 29, 2023

/ok to test

@lowener
Copy link
Contributor Author

lowener commented Oct 2, 2023

AnnCagra/float/uint32_t/35/manual_time       2.52 ms         2.56 ms          277 block_size=256 dataset (GiB)=4.76837 degree=64 graph (GiB)=2.38419 iterations=161 itopk_size=300 k=255 n_cols=128 n_queries=1 n_rows=10M removed_ratio=0 search_width=2
AnnCagra/float/uint32_t/36/manual_time       2.33 ms         2.36 ms          301 block_size=256 dataset (GiB)=4.76837 degree=64 graph (GiB)=2.38419 iterations=161 itopk_size=300 k=255 n_cols=128 n_queries=1 n_rows=10M removed_ratio=0.02 search_width=2
AnnCagra/float/uint32_t/37/manual_time       2.41 ms         2.45 ms          290 block_size=256 dataset (GiB)=4.76837 degree=64 graph (GiB)=2.38419 iterations=161 itopk_size=300 k=255 n_cols=128 n_queries=1 n_rows=10M removed_ratio=0.04 search_width=2
AnnCagra/float/uint32_t/38/manual_time       2.58 ms         2.62 ms          271 block_size=256 dataset (GiB)=4.76837 degree=64 graph (GiB)=2.38419 iterations=161 itopk_size=300 k=255 n_cols=128 n_queries=1 n_rows=10M removed_ratio=0.08 search_width=2
AnnCagra/float/uint32_t/39/manual_time       2.83 ms         2.86 ms          247 block_size=256 dataset (GiB)=4.76837 degree=64 graph (GiB)=2.38419 iterations=161 itopk_size=300 k=255 n_cols=128 n_queries=1 n_rows=10M removed_ratio=0.16 search_width=2
AnnCagra/float/uint32_t/40/manual_time       3.37 ms         3.41 ms          207 block_size=256 dataset (GiB)=4.76837 degree=64 graph (GiB)=2.38419 iterations=161 itopk_size=300 k=255 n_cols=128 n_queries=1 n_rows=10M removed_ratio=0.32 search_width=2
AnnCagra/float/uint32_t/41/manual_time       3.86 ms         3.90 ms          181 block_size=256 dataset (GiB)=4.76837 degree=64 graph (GiB)=2.38419 iterations=161 itopk_size=300 k=255 n_cols=128 n_queries=1 n_rows=10M removed_ratio=0.64 search_width=2
AnnCagra/float/uint32_t/42/manual_time       2.59 ms         2.63 ms          270 block_size=256 dataset (GiB)=4.76837 degree=64 graph (GiB)=2.38419 iterations=161 itopk_size=300 k=255 n_cols=128 n_queries=10 n_rows=10M removed_ratio=0 search_width=2
AnnCagra/float/uint32_t/43/manual_time       2.52 ms         2.56 ms          278 block_size=256 dataset (GiB)=4.76837 degree=64 graph (GiB)=2.38419 iterations=161 itopk_size=300 k=255 n_cols=128 n_queries=10 n_rows=10M removed_ratio=0.02 search_width=2
AnnCagra/float/uint32_t/44/manual_time       2.59 ms         2.63 ms          270 block_size=256 dataset (GiB)=4.76837 degree=64 graph (GiB)=2.38419 iterations=161 itopk_size=300 k=255 n_cols=128 n_queries=10 n_rows=10M removed_ratio=0.04 search_width=2
AnnCagra/float/uint32_t/45/manual_time       2.73 ms         2.77 ms          256 block_size=256 dataset (GiB)=4.76837 degree=64 graph (GiB)=2.38419 iterations=161 itopk_size=300 k=255 n_cols=128 n_queries=10 n_rows=10M removed_ratio=0.08 search_width=2
AnnCagra/float/uint32_t/46/manual_time       3.01 ms         3.05 ms          232 block_size=256 dataset (GiB)=4.76837 degree=64 graph (GiB)=2.38419 iterations=161 itopk_size=300 k=255 n_cols=128 n_queries=10 n_rows=10M removed_ratio=0.16 search_width=2
AnnCagra/float/uint32_t/47/manual_time       3.64 ms         3.67 ms          192 block_size=256 dataset (GiB)=4.76837 degree=64 graph (GiB)=2.38419 iterations=161 itopk_size=300 k=255 n_cols=128 n_queries=10 n_rows=10M removed_ratio=0.32 search_width=2
AnnCagra/float/uint32_t/48/manual_time       4.02 ms         4.06 ms          174 block_size=256 dataset (GiB)=4.76837 degree=64 graph (GiB)=2.38419 iterations=161 itopk_size=300 k=255 n_cols=128 n_queries=10 n_rows=10M removed_ratio=0.64 search_width=2
AnnCagra/float/uint32_t/49/manual_time        485 ms          485 ms            2 block_size=256 dataset (GiB)=4.76837 degree=64 graph (GiB)=2.38419 iterations=161 itopk_size=300 k=255 n_cols=128 n_queries=10k n_rows=10M removed_ratio=0 search_width=2
AnnCagra/float/uint32_t/50/manual_time        632 ms          631 ms            1 block_size=256 dataset (GiB)=4.76837 degree=64 graph (GiB)=2.38419 iterations=161 itopk_size=300 k=255 n_cols=128 n_queries=10k n_rows=10M removed_ratio=0.02 search_width=2
AnnCagra/float/uint32_t/51/manual_time        629 ms          629 ms            1 block_size=256 dataset (GiB)=4.76837 degree=64 graph (GiB)=2.38419 iterations=161 itopk_size=300 k=255 n_cols=128 n_queries=10k n_rows=10M removed_ratio=0.04 search_width=2
AnnCagra/float/uint32_t/52/manual_time        631 ms          624 ms            1 block_size=256 dataset (GiB)=4.76837 degree=64 graph (GiB)=2.38419 iterations=161 itopk_size=300 k=255 n_cols=128 n_queries=10k n_rows=10M removed_ratio=0.08 search_width=2
AnnCagra/float/uint32_t/53/manual_time        617 ms          617 ms            1 block_size=256 dataset (GiB)=4.76837 degree=64 graph (GiB)=2.38419 iterations=161 itopk_size=300 k=255 n_cols=128 n_queries=10k n_rows=10M removed_ratio=0.16 search_width=2
AnnCagra/float/uint32_t/54/manual_time        608 ms          607 ms            1 block_size=256 dataset (GiB)=4.76837 degree=64 graph (GiB)=2.38419 iterations=161 itopk_size=300 k=255 n_cols=128 n_queries=10k n_rows=10M removed_ratio=0.32 search_width=2
AnnCagra/float/uint32_t/55/manual_time        605 ms          604 ms            1 block_size=256 dataset (GiB)=4.76837 degree=64 graph (GiB)=2.38419 iterations=161 itopk_size=300 k=255 n_cols=128 n_queries=10k n_rows=10M removed_ratio=0.64 search_width=2

@lowener
Copy link
Contributor Author

lowener commented Oct 2, 2023

/ok to test

raydouglass pushed a commit that referenced this pull request Oct 2, 2023
This PR fixes a bug in the filtering operations in the CAGRA multi-kernel search implementation. This bug caused the test of #1837 to fail.

Authors:
   - tsuki (https://github.com/enp1s0)

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

@cjnolet cjnolet left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

LGTM!

@cjnolet
Copy link
Member

cjnolet commented Oct 2, 2023

@lowener, I've approved this PR and I think the implementation looks good. The only thing lacking now is documentation. We should add a separate usage example to raft::cagra::search_with_filtering for specifying the bitset sample filter.

@lowener
Copy link
Contributor Author

lowener commented Oct 2, 2023

/ok to test

@cjnolet
Copy link
Member

cjnolet commented Oct 2, 2023

/ok to test

@raydouglass raydouglass merged commit bf3f85a into rapidsai:branch-23.10 Oct 3, 2023
54 of 56 checks passed
@lowener lowener deleted the 23.10-cagra-remove branch November 3, 2023 13:12
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
3 - Ready for Review cpp feature request New feature or request non-breaking Non-breaking change
Projects
Development

Successfully merging this pull request may close these issues.

[FEA] Support vector deletion in CAGRA
4 participants