To Reveal the Performance Secrets of the Newest NN Searching Algorithm

Nearest Neighbor (NN) search has been widely used in spatial databases and multimedia databases. Incremental NN (INN) search algorithm is regarded as the optimal NN search because of the minimum number of node accesses and it can be used no matter whether the number of objects to be retrieved is fixed or not in advance. This paper presents an analytical model for estimating performance of the INN search algorithm. For the first time, the authors' model takes m (the number of neighbor objects reported finally), n (the cardinality of database) and d (the dimensionality) as parameters, focusing on the number of node accesses (not only the number of accessed leaf nodes) and the length of the priority queue.