Querying the training set: runtime tradeoff for large k

Nobody has claimed this yet.

Thanks for the package and excellent documentation!

I have a question about the best way to optimize performance (speed up without debilitating loss to accuracy) for my use case. Any insight you could provide would be much appreciated.

I'm using PyNNDescent as the blocking step in a record linkage algorithm. Specifically, I have a list of ~1M names (first and last) that I have converted into vector space by getting pairs of adjacent letters. E.g. "JOHN SMITH" becomes ["JO", "OH", "HN", "N ", " S", "SM", "MI", "IT", "TH"]. For each name, I want to get a complete list of similar names (something like all names with cosine distance < 0.4).

I believe I am in the scenario outlined in the "Nearest neighbors of the training set" section of the documentation, in that I know all of the names I want to query at the time of index creation. However, because I have a lot of names and I'm wanting to use a fairly high cosine distance threshold I have to set `k` to something pretty high like 300. Naturally this causes the index creation step to take a very long time, but eliminates the query time entirely.

My question is whether you think in this case it would be more efficient to build the index with a smaller `k` and then query all the points in the index with the larger `k=300` value. Or do you have any other suggestions for how to minimize runtime for this use case?

Start with the documentation's “Nearest neighbors of the training set” section and trace the index-construction and query entry points it describes. Compare the runtime and accuracy implications of a smaller construction k followed by queries at k=300 for the stated million-name, cosine-distance workload. Done means a documented recommendation or measured tradeoff for this use case.

Written by the indexing model from the issue text.