Testing against a newer version of NMSLIB

[searchivarius]

Hi guys, nice work (a good selection of data sets as well). We have updated our algorithms, so you may want to rely on the latest version 1.5.1: https://github.com/searchivarius/nmslib
PS: I am also glad that RCT is now publicly available.

[searchivarius]

More specific notes:

1. It is not the most efficient way to test SW-graph by increasing the number of search attempts. Yes, we did it is so for the VLDB paper, but it is possible to do much better. In fact, as @yurymalkov demonstrated, it is nearly always better to use a single search.
2. When we first participated in ann-benchmarks 3 years ago, we used an improved version of SW-graph that was about 3 times more efficient. This version was better than both k-graph and Annoy when parameters are properly tuned. One reason, why it was so efficient is because we adopted some of the algorithmic k-graph tricks. This brings us to item.
3. While I agree that using multi-threading and GPU at test time isn't fair, it is not easy to get insights into algorithm performance by simply disabling SIMD, prefetching, or diabling optimized memory layouts. For example, Wei Dong used a more efficient way to check if the node was visited. If you want to be absolutely fair, you need to implement several algorithm of graph construction and several searching algorithms.
4. The current SW-graph version is nearly 10 times more efficient compared to the VLDB version. But this is not all. @yurymalkov proposed a novel variant of the proximity/neighborhood graph, which is even 3-10 times more efficient. Not all of this an algorithmic improvement, but most of it is.
5. Regarding performance of VP-tree on SIFT. I can nearly reproduce your results on Audio, but not on SIFT. In particular, for recall-0.9 I get 15x improvement and for recall=0.2, I get 1000x improvement (I also use k=20). For low recall values, Annoy, FLANN, and VP-tree actually converge. This is confirmed by ann-benchmark results.
6. Disabling SIMD may not be as simple as you describe. The compiler tends to insert SIMD code automatically. I suspect this may happen even if you don't specify some of the flags. So, instead of trying to disable SIMD, you better make sure that all algorithms use the same implementation of the distance function. In any case, your alogrithms run on actuall CPUs and real CPUs all have SIMD nowdays.

If you fail to disable SIMD in some code, but not in the other, this may give an advantage to some of the implementations. Why? Because, faster computations of the distance means that all the other operations take longer time relative to the computations of the distance. If the distance is more expensive to compute, the overhead time contributes less to the overall time. So, if you disable successfully SIMD in algorithm A, you decrease the overhead. However, if you fail to do so in algorithm B, the overhead is the same.

1. Please, specify k for each figure. This seems to be important as you use different.

PS: it will also be beneficial to use larger data sets. After looking at the data sets more carefully, I noticed a lot of the data sets are quite small.

[DBWangWei]

Hi Leonid,

Thanks for your comments. Glad to know the new version of NMSLIB is available now, and we will find a time to re-evaluate the related algorithms in the new version.

Some quick replies on the issues you raised:

1. SW-graph. We tune the algorithm according to the suggestion in the paper. I think it was suggest that multiple attempts (m > 10) leads to a good recall. I skimmed through the manual in the new library. We will use the new parameters for tuning. I just want to quickly point out one key difference: we want to evaluate the tradeoff between time/points-examined and recall on the SAME index. Hence, we are not going to tune parameters that lead to a different index.
2. Regarding the performance comparison between SW-graph and KGraph.
   We have some discussions about the difference performance evaluation results reported in ANN-benchmark and our NNS-benchmark in Section 9.3 of our current (technique report)[http://www.cse.unsw.edu.au/~yingz/NNS.pdf].
3. Regarding the fairness. In addition to disabling the compile flag, we also remove the SIMD related code in KGraph and DPG, that means we use the same distance implementation for the algorithms. Considering we use the same compiler and run all algorithms on the same machine, even if SIMD related optimization is activated by the system implicitly, that should be equal to all implementation.

Ideally, it would be a fairer comparison if we re-implement every algorithm in the most efficient way. However, we do not have the luxury to do this. Besides, relying on authors' own implementation means that it is easier to adapt to their latest versions.

Finally, we also evaluate number of points examined by the algorithms, which is agnostic to the implementation details, and can be deemed as a (not-ideal but) good approximation to the efficiency in most of the cases.

1. Regarding performance of VP-tree on SIFT.

Just wonder if you have run our version, which disabled some optimizations? It seems we already use the same tuning approach with the early version of NMSLIB.

1. k values.

The default k value in each k-NN search is 20. In our TR, we also evaluate the impact of different k.

Or are you referring to another parameter (\kappa?)

Wei

[searchivarius]

Dear Wei,

Thank you for the clarificaiton. I have sent you a more detailed explanation by e-mail. Here's I only quickly go over some of the points.

1.1 Don't forget that the paper was written before k-graph was open sourced and before the first ann-benchmark. The paper was focused on comparing against different methods for which having faster SW-graph didn't change results qualitatively. It wasn't even possible to change the paper at the moment when ann-benchmark started.
1.2 However, if you test on SIFT and glove, the parameters set for ann-benchmark are, perhaps, the best. You can test against the single index. It is not always optimal though. Why do you always need a single index?
2. Regarding comparison between k-graph and SW-graph. Sorry, I don't quite understand the arguments. In my e-mail I go into more detail.

Regarding the number of points evaluated: while this characteristic is overly optimistic for filter-and-refine method, it may be ok for proximity graphs. Did you compute this number when you compared SW-graph vs k-graph? The only plot that contains data on the number of points evaluated seems to be Figure 40. However, it doesn't contain SW-graph.

Regarding VP-tree. It's not competitive for high-recall values. It's just a check point. I didn't run your version. I wonder why it is so much slower. See, e.g., the results from ann_benchmark. I get the same results using NMSLIB. Sequential search is 10 QPS, so you can infer that the speed-up ranges from 10 to 1000, while in your paper it ranges from 1 to 100:

Regrading k: I am just saying that adding the value of k to table captions will be helpful.