maximum inner product search (MIPS)

[Chen-Cai-OSU]

Hello,

Thank you very much for the amazing work. I really like extensive experiments in your paper. I was wondering have you ever looked at MIPS? https://ai.googleblog.com/2020/07/announcing-scann-efficient-vector.html

It's also a very important problem and I am curious that the performance compared to other solutions such as scann and faiss. I am interested in both brute force and none brute-force approaches, just like KNN in your paper.

I also want to confirm one thing with you:

• The KNN (or MIPS) implementation in Keops can be put inside a deep learning model in pytorch, right?

Thank you!

[jeanfeydy]

Hi @Chen-Cai-OSU ,

Thanks for your interest in the library!
Indeed, this is a problem that we have worked on quite a bit: in our KNN benchmarks, we refer to MIPS as to "KNN search with a cosine similarity". (Note that we tend to normalize vectors in these benchmarks, but this has no influence on run times for bruteforce implementations.)

To answer your questions:

• Yes, KeOps is fully compatible with deep learning in PyTorch.
• Currently, bruteforce KeOps implementations are extremely competitive for KNN and MIPS on data sets that have less than 1M samples in dimension D<50, as well as non-Euclidean metrics.
• Between January and May, I have worked with an excellent group of students at Imperial College to start adding support for non-bruteforce methods in KeOps. Their code is available in the pull request Knn and nystrom #143 and provides an equivalent to the FAISS "IVF-Flat" strategy for KNN/MIPS with any metric: I will merge it into the KeOps master branch over the summer.

What do you think?
Best regards,
Jean

[Chen-Cai-OSU]

Thank you so much! KeOps looks amazing. And your answer clears out some of my doubts. I will definitely take a try.

My dataset can be quite large: 100M samples with D=64. I will start with some sampling and move to full dataset. Will use this thread to keep you updated.

[jeanfeydy]

I see! Good luck then, and please let us know about your experience with KeOps on such a large-scale problem :-)

Best regards,
Jean