On efficiency of the hierarchical algorithm for searching approximate nearest neighbor in a given set of images

The efficiency of the hierarchical algorithm for searching approximate nearest neighbor in a given set of images subject to an unwarranted error about the nearest image is investigated. The algorithm uses a space of quad pyramidal image representations as well as a guided search strategy in successive representation levels of increasing resolution. The efficiency is studied in terms of both an empirical distribution of search errors and computational complexity of the hierarchical algorithm relative to the exhaustive search. The above characteristics are obtained for two applications, namely, search for approximate nearest image in a set of hand-written digits from the MNIST data base and gridding a given noisy image in an aerospace digital map from the Google maps network service.