This paper presents an asymptotic analysis for the nearest neighbor search with
pivot-based indexes. We extend a previous analysis based on range queries with
fixed tolerance radius, because there is a probability that the nearest
neighbor is missed. We introduce a probabilistic analysis and then we show the
expected search cost for range-optimal algorithms. Finally, we also show the
analysis of the proposed search algorithm taking into account the extra CPU
time, which leads to further insights on the efficiency of different
implementations of this algorithm.