Efficient search scheme for very large image databases
Sakti K. Pramanik, Jinhua Li, Jiandong Ruan, Sushil Bhattacharjee · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · 1999
Nearest Neighbor search is a fundamental task in many applications. At present state of the art, approaches to nearest neighbor search are not efficient in high dimensions. In this paper we present an efficient angle based balanced index structure called AB-tree, which uses heuristics to decide whether or not to access a node in the index tree based on the estimated angle and the weight of the node. We have presented the result of AB-tree for up to 64 dimensions, and have shown that the performance of the AB-tree algorithm does not deteriorate when processing nearest neighbor queries as dimension increases. However, it is no longer guaranteed that the entire true K nearest neighbors to a query point will be found. Extensive experiments on synthetic data and real data demonstrate that the search time is improved by a factor of up to 85 times over that of SS-tree in 64 dimension while maintaining 90 percent accuracy. Real data includes color histogram and corner like features in a heterogenous collection of natural images.