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

Can HNSWPQ nbits parameter be made configurable? #3027

Closed
jmazanec15 opened this issue Aug 24, 2023 · 2 comments
Closed

Can HNSWPQ nbits parameter be made configurable? #3027

jmazanec15 opened this issue Aug 24, 2023 · 2 comments
Labels
enhancement

Comments

@jmazanec15
Copy link
Contributor

Summary

For IndexHNSWPQ, I see the value for nbits is hardcoded to 8. I wanted to know if this could possibly be made configurable?

I saw this issue from several years ago: #259, where reasoning for not going above 8 nbits on CPU was over concerns of keeping table in l1/l2 cache. However, I am wondering if improved recall may be worth the tradeoff in additional latency. Additionally, for graph-based algorithms, where fewer distance computations are made, I am wondering if the latency impact from not fitting table in l1 cache may not be as pronounced.
@jmazanec15 jmazanec15 mentioned this issue Aug 24, 2023
Closed
@mdouze
Copy link
Contributor

mdouze commented Aug 28, 2023

Suppport for >8 bits per PQ has improved a lot, so we should support it in HNSW as well.

Easy to address here with a default value of 8

https://github.com/facebookresearch/faiss/blob/main/faiss/IndexHNSW.cpp#L889

the only issue is that the PQ parameters are intermixed with the HNSW parameters but there is no easy way around it wihtout breaking compatibiiuty.

@jmazanec15
Copy link
Contributor Author

Sure, let me see if I can make the change without breaking bwc. I assume that we could use default of 8 as a way to avoid this in most cases.

jmazanec15 added a commit to jmazanec15/k-NN-1 that referenced this issue Aug 30, 2023
@jmazanec15
Update Faiss engine to allow PQ and HNSW
5118481 
Updates faiss engine to enable hnsw and faiss to work together. For
HNSW, code_size must be equal to 8 (refer to
facebookresearch/faiss#3027). Therefore, the
index description string "HNSW32,PQXxY" does not work. Only "HNSW32,PQX"
ends up working.

Additionally, adds several unit tests and integration tests in order to
validate the functionality.

Signed-off-by: John Mazanec <jmazane@amazon.com>
jmazanec15 added a commit to jmazanec15/k-NN-1 that referenced this issue Aug 30, 2023
@jmazanec15
Update Faiss engine to allow PQ and HNSW
1db5282 
Updates faiss engine to enable hnsw and faiss to work together. For
HNSW, code_size must be equal to 8 (refer to
facebookresearch/faiss#3027). Therefore, the
index description string "HNSW32,PQXxY" does not work. Only "HNSW32,PQX"
ends up working.

Additionally, adds several unit tests and integration tests in order to
validate the functionality.

Signed-off-by: John Mazanec <jmazane@amazon.com>
@jmazanec15 jmazanec15 mentioned this issue Aug 30, 2023
Merged
5 tasks
jmazanec15 added a commit to jmazanec15/k-NN-1 that referenced this issue Aug 30, 2023
@jmazanec15
Update Faiss engine to allow PQ and HNSW
f2754ca 
Updates faiss engine to enable hnsw and faiss to work together. For
HNSW, code_size must be equal to 8 (refer to
facebookresearch/faiss#3027). Therefore, the
index description string "HNSW32,PQXxY" does not work. Only "HNSW32,PQX"
ends up working.

Additionally, adds several unit tests and integration tests in order to
validate the functionality.

Signed-off-by: John Mazanec <jmazane@amazon.com>
jmazanec15 added a commit to jmazanec15/k-NN-1 that referenced this issue Aug 30, 2023
@jmazanec15
Update Faiss engine to allow PQ and HNSW
f71fb24 
Updates faiss engine to enable hnsw and faiss to work together. For
HNSW, code_size must be equal to 8 (refer to
facebookresearch/faiss#3027). Therefore, the
index description string "HNSW32,PQXxY" does not work. Only "HNSW32,PQX"
ends up working.

Additionally, adds several unit tests and integration tests in order to
validate the functionality.

Signed-off-by: John Mazanec <jmazane@amazon.com>
jmazanec15 added a commit to jmazanec15/k-NN-1 that referenced this issue Aug 30, 2023
@jmazanec15
Update Faiss engine to allow PQ and HNSW
c0e2297 
Updates faiss engine to enable hnsw and faiss to work together. For
HNSW, code_size must be equal to 8 (refer to
facebookresearch/faiss#3027). Therefore, the
index description string "HNSW32,PQXxY" does not work. Only "HNSW32,PQX"
ends up working.

Additionally, adds several unit tests and integration tests in order to
validate the functionality.

Signed-off-by: John Mazanec <jmazane@amazon.com>
jmazanec15 added a commit to opensearch-project/k-NN that referenced this issue Aug 30, 2023
@jmazanec15
Update Faiss engine to allow PQ and HNSW (#1074)
ce47b1b 
Updates faiss engine to enable hnsw and faiss to work together. For
HNSW, code_size must be equal to 8 (refer to
facebookresearch/faiss#3027). Therefore, the
index description string "HNSW32,PQXxY" does not work. Only "HNSW32,PQX"
ends up working.

Additionally, adds several unit tests and integration tests in order to
validate the functionality.

Signed-off-by: John Mazanec <jmazane@amazon.com>
jmazanec15 added a commit to jmazanec15/k-NN-1 that referenced this issue Aug 30, 2023
@jmazanec15
Update Faiss engine to allow PQ and HNSW (opensearch-project#1074)
ee2444e 
Updates faiss engine to enable hnsw and faiss to work together. For
HNSW, code_size must be equal to 8 (refer to
facebookresearch/faiss#3027). Therefore, the
index description string "HNSW32,PQXxY" does not work. Only "HNSW32,PQX"
ends up working.

Additionally, adds several unit tests and integration tests in order to
validate the functionality.

Signed-off-by: John Mazanec <jmazane@amazon.com>
(cherry picked from commit ce47b1b)
jmazanec15 added a commit to jmazanec15/k-NN-1 that referenced this issue Aug 31, 2023
@jmazanec15
Update Faiss engine to allow PQ and HNSW (opensearch-project#1074)
b0b3d6b 
Updates faiss engine to enable hnsw and faiss to work together. For
HNSW, code_size must be equal to 8 (refer to
facebookresearch/faiss#3027). Therefore, the
index description string "HNSW32,PQXxY" does not work. Only "HNSW32,PQX"
ends up working.

Additionally, adds several unit tests and integration tests in order to
validate the functionality.

Signed-off-by: John Mazanec <jmazane@amazon.com>
(cherry picked from commit ce47b1b)
jmazanec15 added a commit to jmazanec15/k-NN-1 that referenced this issue Aug 31, 2023
@jmazanec15
Update Faiss engine to allow PQ and HNSW (opensearch-project#1074)
f0dfb8d 
Updates faiss engine to enable hnsw and faiss to work together. For
HNSW, code_size must be equal to 8 (refer to
facebookresearch/faiss#3027). Therefore, the
index description string "HNSW32,PQXxY" does not work. Only "HNSW32,PQX"
ends up working.

Additionally, adds several unit tests and integration tests in order to
validate the functionality.

Signed-off-by: John Mazanec <jmazane@amazon.com>
(cherry picked from commit ce47b1b)
jmazanec15 added a commit to jmazanec15/k-NN-1 that referenced this issue Aug 31, 2023
@jmazanec15
Update Faiss engine to allow PQ and HNSW (opensearch-project#1074)
cebc358 
Updates faiss engine to enable hnsw and faiss to work together. For
HNSW, code_size must be equal to 8 (refer to
facebookresearch/faiss#3027). Therefore, the
index description string "HNSW32,PQXxY" does not work. Only "HNSW32,PQX"
ends up working.

Additionally, adds several unit tests and integration tests in order to
validate the functionality.

Signed-off-by: John Mazanec <jmazane@amazon.com>
(cherry picked from commit ce47b1b)
jmazanec15 added a commit to jmazanec15/k-NN-1 that referenced this issue Aug 31, 2023
@jmazanec15
Update Faiss engine to allow PQ and HNSW (opensearch-project#1074)
3df15d9 
Updates faiss engine to enable hnsw and faiss to work together. For
HNSW, code_size must be equal to 8 (refer to
facebookresearch/faiss#3027). Therefore, the
index description string "HNSW32,PQXxY" does not work. Only "HNSW32,PQX"
ends up working.

Additionally, adds several unit tests and integration tests in order to
validate the functionality.

Signed-off-by: John Mazanec <jmazane@amazon.com>
jmazanec15 added a commit to jmazanec15/k-NN-1 that referenced this issue Aug 31, 2023
@jmazanec15
Update Faiss engine to allow PQ and HNSW (opensearch-project#1074)
2439a8a 
Updates faiss engine to enable hnsw and faiss to work together. For
HNSW, code_size must be equal to 8 (refer to
facebookresearch/faiss#3027). Therefore, the
index description string "HNSW32,PQXxY" does not work. Only "HNSW32,PQX"
ends up working.

Additionally, adds several unit tests and integration tests in order to
validate the functionality.

Signed-off-by: John Mazanec <jmazane@amazon.com>
@mdouze mdouze mentioned this issue Aug 31, 2023
Closed
mdouze added a commit to mdouze/faiss that referenced this issue Aug 31, 2023
@mdouze @facebook-github-bot
make nbits configurable for graph indices based on PQ
0fed833 
Summary:
As requested in

facebookresearch#3027

Indeed, PQ sizes with nbits > 8 are good tradeoffs, so it is interesting to support them.

Differential Revision: D48860659

fbshipit-source-id: 4956fdf5a442dae0a206478e211a72108c85c284
mdouze added a commit to mdouze/faiss that referenced this issue Aug 31, 2023
@mdouze @facebook-github-bot
make nbits configurable for graph indices based on PQ (facebookresear…
5222d49 
…ch#3031)

Summary:
Pull Request resolved: facebookresearch#3031

As requested in

facebookresearch#3027

Indeed, PQ sizes with nbits > 8 are good tradeoffs, so it is interesting to support them.

Differential Revision: D48860659

fbshipit-source-id: 5cd679a4a62f3c9177962481679aa85e88827cc4
jmazanec15 added a commit to opensearch-project/k-NN that referenced this issue Aug 31, 2023
@jmazanec15
Update Faiss engine to allow PQ and HNSW (#1074)
765ccc3 
Updates faiss engine to enable hnsw and faiss to work together. For
HNSW, code_size must be equal to 8 (refer to
facebookresearch/faiss#3027). Therefore, the
index description string "HNSW32,PQXxY" does not work. Only "HNSW32,PQX"
ends up working.

Additionally, adds several unit tests and integration tests in order to
validate the functionality.

Signed-off-by: John Mazanec <jmazane@amazon.com>
jmazanec15 added a commit to opensearch-project/k-NN that referenced this issue Aug 31, 2023
@jmazanec15
Update Faiss engine to allow PQ and HNSW (#1074)
a67e987 
Updates faiss engine to enable hnsw and faiss to work together. For
HNSW, code_size must be equal to 8 (refer to
facebookresearch/faiss#3027). Therefore, the
index description string "HNSW32,PQXxY" does not work. Only "HNSW32,PQX"
ends up working.

Additionally, adds several unit tests and integration tests in order to
validate the functionality.

Signed-off-by: John Mazanec <jmazane@amazon.com>
facebook-github-bot pushed a commit that referenced this issue Sep 1, 2023
@mdouze @facebook-github-bot
make nbits configurable for graph indices based on PQ (#3031)
82352dd 
Summary:
Pull Request resolved: #3031

As requested in

#3027

Indeed, PQ sizes with nbits > 8 are good tradeoffs, so it is interesting to support them.

Reviewed By: pemazare

Differential Revision: D48860659

fbshipit-source-id: 6f3c642e0902e1523bef36db6be3af3688d529a5
@kuarora kuarora closed this as completed Apr 3, 2024
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
enhancement
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
3 participants
@kuarora @jmazanec15 @mdouze