Paper: Efficient and robust approximate nearest neighbor search using Hierarchical Navigable Small World graphs

In the Search Complexity section, the author estimates that the expected number of steps in a layer is bounded by $1/(1 - exp(-m_{L})$. It says:

There is a fixed probability $p=exp(-m_{L} )$ that the next node belongs to the upper layer. However, the search on the layer always terminates before it reaches the element which belongs to the higher layer (otherwise the search on the upper layer would have stopped on a different element), so the probability of not reaching the target on s-th step is bounded by $exp(-s· m_{L} )$.

Shouldn't the probability of reaching the target on s-th step be $(1-exp(-m_{L}))^{s} *exp(-m_{L})$ since this would mean we are reaching a node which belongs to higher layer on the (s+1)th hop ? If yes, doesn't it defy the bound introduced in the above paragraph ?

  • $\begingroup$ Hello. You can use latex/mathjax on this site. I recommend that you edit your post to format your symbols and equations with it to improve the readability. You can also prepend the quotes with > to make it clear it's a quote. $\endgroup$
    – nbro
    Feb 28 at 0:24
  • 1
    $\begingroup$ Thanks @nbro, edited. $\endgroup$
    – p1p13
    Feb 28 at 8:33


You must log in to answer this question.

Browse other questions tagged .