View publication
| Title | On the Asymptotic Behavior of Nearest Neighbor Search using Pivot-Based Indexes |
| Authors | Benjamin Bustos, Nelson Morales |
| Publication date | 2010 |
| Abstract | 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. |
| Downloaded | 17 times |
| Pages | 33-39 |
| Conference name | International Workshop on Similarity Search and Applications |
| Publisher | IEEE Computer Society Press (Los Alamitos, CA, USA) |
|
|
| Reference URL |
|