3
$\begingroup$

Question on embedding similarity / nearest neighbor methods:

In https://arxiv.org/abs/2112.04426 the DeepMind team writes:

For a database of T elements, we can query the approximate nearest neighbors in O(log(T)) time. We use the SCaNN library [https://ai.googleblog.com/2020/07/announcing-scann-efficient-vector.html]

Could someone provide an intuitive explanation for this time complexity of ANN?

Thanks!

A very Happy New Year Earthling's!

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ the trick for this complexity is approximate nearest neighbors. Possibly it refers to some previous paper where this would be derived $\endgroup$
    – Nikos M.
    Jan 1, 2022 at 12:20
  • $\begingroup$ Yep, the trick definitely comes from the approximate part but I am curious which paper from the references should help me with it? Thanks $\endgroup$
    – Aditya
    Jan 1, 2022 at 13:54
  • $\begingroup$ The logarithm in the complexity implies some data structure similar to tree search or binary search, which have logarithmic complexity assuming the inputs are somehow sorted $\endgroup$
    – Nikos M.
    Jan 1, 2022 at 16:25
  • $\begingroup$ Yep, something like binary search on some cool indexing trick should do the job $\endgroup$
    – Aditya
    Jan 1, 2022 at 16:40

1 Answer 1

Reset to default
2
$\begingroup$

It is a shame they don't give a better reference for their O(log(N)) isn't it.

You asked for papers, and the obvious starting point is the one the SCaNN library is based on: https://arxiv.org/abs/1908.10396

What they say there (section 4) is:

After we quantize a database of n points, we can calculate the dot product of a query vector q with all quantized points in O(kd+ n) time. This is much better than the O(nd) time required for the original unquantized database

The next useful place to read is https://github.com/google-research/google-research/blob/master/scann/docs/algorithms.md

They partition large datasets using a tree. So there is an obvious O(log(N)) search complexity. For the 2 trillion token dataset in the 2112.04426 paper, the square root recommendation on that github page implies around 1.5 million partitions.

They also give a reference there for product quantization for approximate neighbour search: https://lear.inrialpes.fr/pubs/2011/JDS11/jegou_searching_with_quantization.pdf

Table II compares the time to find the k smallest distances, between SDC and ADC. (I am assuming the ADC there is the same as the AH, asymmetric hashing, used in ScaNN.) Unfortunately table II is badly formatted, and the two cells run into each other (?).

However I tracked down basically the same paper by the same author, https://hal.inria.fr/inria-00410767/document/ , which has a Table 2 that says the complexity is n + k log n.

Which doesn't resemble anything in Table II in the other paper, and also isn't O(kd+n). A bit unsatisfying.

But, overall, I assume that the O(log(N)) claim is based on the tree search of the partitions. And then once you are searching inside each partition, it is effectively O(kd + √N), which is small enough to throw away?

Improve this answer
$\endgroup$
6
  • $\begingroup$ I am curious, how come we throw the last term that you have mentioned? If that particular partion which you get after tree search is a "hot" partition, then we can't throw the last complexity mentioned away. Is my understanding incorrect? Thanks for your answer! $\endgroup$
    – Aditya
    Jan 13, 2022 at 16:55
  • 1
    $\begingroup$ @Aditya My thinking was that the partition part of the search is over, say, a trillion items; whereas the search within a partition is done over only a million items. So in terms of actual milliseconds spent, the former dominates, and that is the part with log(N) complexity. So this was more about trying to explain why they wrote log(N), instead of something like O(log(N)kd + log(N)√N) $\endgroup$
    – Darren Cook
    Jan 14, 2022 at 8:29
  • $\begingroup$ Oh i see now what you meant, thanks for the explaination! $\endgroup$
    – Aditya
    Jan 14, 2022 at 8:32
  • $\begingroup$ As @Aditya observed sqrt(N) grows much faster than log(N). As far as I understand O(log(N)) complexity is theoretically proved only for LSH type methods (papers of Kushilevitz, Ostrovsky, Rabani / Andoni, Indyk, Patrascu), while scann is mainly concerned with practical performance and it's theoretical worst case complexity is unproved/unpublished/does not hold. $\endgroup$
    – Valentas
    May 13, 2022 at 15:13
  • $\begingroup$ @Valentas Yes, I still find their O(log(N)) claim a bit imprecise. $\endgroup$
    – Darren Cook
    May 13, 2022 at 15:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.