estimation of hubs after building index

[jianshu93]

Hi @BlaiseMuhirwa,

I realized that the detailed analysis of hubs across different dataset is very useful. Is there a way to have a rough estimation of the number of hubs for a give dataset after building the graph, similar to the original hubness paper? Could be very useful for us to know how many hubs might be playing role for searching step.

Best,
Jianshu

[BlaiseMuhirwa]

Hi @jianshu93

Thanks for the question. I'd recommend you take a look at the hubs in space paper, which defines the hubness of a given dataset based on the skewness of the k-occurrence distribution (i.e., how often each datapoint appears in the nearest neighbor set of other data points). This is of course computationally expensive.

The simplest way to estimate this is to sample a smaller subset of your nodes/vectors and use those to compute the skewness of the k-occurrence distribution. For instance, if you have a dataset like SIFT 1M, using 10K nodes is a reasonable number to use. How many nodes you use depends of course on your requirements (how accurate you want this hubness score and how fast you want the computation to take).

[jianshu93]

hi @BlaiseMuhirwa,
I was asking because in our Rust HNSW implementation, we were able to do this, yes, we did a sampling exactly as what you've suggested. Accordingly, the paper can be found here: https://academic.oup.com/nargab/article/6/4/lqae172/7928174. It was designed to see how many LID or hubs biological datasets may have but it turns out to be working for any dataset.

Best,
Jianshu

[BlaiseMuhirwa]

Makes sense. You mentioned that sampling and computing the hubness score worked for any dataset. Are you looking to estimate this score faster?

[jianshu93]

Yeah and also want to know before search possible number of hubs will be used， just an approximate， no need to be that accurate.

Jianshu