20 December 1999 Efficient search scheme for very large image databases
Author Affiliations +
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.
© (1999) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Sakti K. Pramanik, Sakti K. Pramanik, Jinhua Li, Jinhua Li, Jiandong Ruan, Jiandong Ruan, Sushil K. Bhattacharjee, Sushil K. Bhattacharjee, } "Efficient search scheme for very large image databases", Proc. SPIE 3964, Internet Imaging, (20 December 1999); doi: 10.1117/12.373479; https://doi.org/10.1117/12.373479

Back to Top