bad recall performance

[tangchen2]

i build hnsw index ( cosine distance ) based on 1000w data, however, the recall performance is bad, some query data (cosine distance very small ) not be recalled, while some other unrelated data recalled.
would num_threads, M, cef or sef affect the hnsw recall? (BTW in my experiment, M=72, cef=200, sef=2000)

[yurymalkov]

@tangchen2 Typically efConstruction should be bigger or equal compared to ef, so that might be one of the issues.
I wonder, does your data have duplicates (elements with almost exact values)? If so, deduping should bring a huge performance/accuracy gain.

[Jowekk]

I also encountered this problem, and I felt that hnsw's recall under the large data set was seriously reduced.

I have 5000 pairs of face matching features. I mix one 5000 into completely unrelated face gallery data sets and use the other 5000 to retrieve them.

M = 48, efConstruction = 200, feature dim = 384.

Here are the results of HNSW:

gallery size: 1 million
top[1]=0.772950
top[5]=0.818441
top[10]=0.836393
top[20]=0.850265
top[50]=0.866585
top[100]=0.880661
top[256]=0.894941
top[512]=0.906365
top[1024]=0.915749

gallery size: 5 million
top[1]=0.672787
top[5]=0.714810
top[10]=0.728070
top[20]=0.741942
top[50]=0.758262
top[100]=0.767238
top[256]=0.777642
top[512]=0.785190
top[1024]=0.790698

Here is the search result of GPU flat for comparison:

gallery size: 5 million
top[1]=0.725622
top[5]=0.780090
top[10]=0.801102
top[20]=0.821297
top[50]=0.847001
top[100]=0.861485
top[256]=0.879845
top[512]=0.893921
top[1024]=0.907181

Is there something wrong with me?
If necessary, I can open my data sets.

[Jowekk]

I checked this discussion https://github.com/nmslib/hnswlib/issues/164.
As to whether there are duplicate data, I use 5 million gallery data sets to retrieve themselves:

top 1: 4861229/5000000 = 0.972246
top 5: 4999996/5000000 = 0.999999
top 10: 5000000/5000000 = 1
top 20: 5000000/5000000 = 1
top 50: 5000000/5000000 = 1

It can be seen that there is a little duplicate data in my gallery data sets, but most of them still don't seem to be repeated.
If there are other experimental details that need to be supplemented, I can provide corresponding experiments.

[yurymalkov]

@Jowekk I am not sure I understand. The recall you measure is the recall of the full ML pipeline for the same person?

[Jowekk]

5000 pairs: paired images taken by 5000 different people.
gallery data: completely unrelated to the above 5000 people.

I used 5000 images as batch queries to recall the other 5000 paired images.
If top one hits 1000, then top[1] = 1000 / 5000 = 0.2
Did I describe it clearly？

[yurymalkov]

@Jowekk I see, didn't notice you have brute force results.
I wonder, did you try to alter the ef parameter (and what happens if you set it to say, 10000).

[Jowekk]

ef = 10000 is too big to meet our time requirements.
When ef and gallery size are increased, a large number of random accesses will be caused because neighbors are randomly stored in memory.
Bottlenecks accessed randomly allowed QPS to fall quickly.
Do you think the number of neighbors scanned is too small？
Here is a small experiment, the number of scans on neighbors in different gallery size:

gallery size	10,000	100,000	1000,000
scan num of neighbors	9049	29881	49351

[yurymalkov]

Looking on how recall changes with ef, while keeping other parameters fixed provides diagnostic information.
E.g. if ef is extremely large and recall is low that hints the graph has disconnected components, etc

[Jowekk]

ok, this is a good idea worth trying. thank u