A new strategy for nearest neighbor search is presented by the authors that offers fast and early-terminated query evaluation in a network environment, where the data is located remotely, and the search process is supposed to be shared by local, remote, and possibly some intermediate hosts. The strategy involves a multi-level approximation scheme. Each level receives a candidate set of items from its predecessor, and refines the set by applying a more accurate approximation to filter out undesired items. In addition to this process, each level also returns an item along with a number, M, with the guarantee that the item is one of the M nearest neighbors, with M being strictly reduced level after level. Thus, a user might stop whenever he or she feels satisfied, or when M=1.

The approximation is done by mathematically estimating the lower and upper bounds for the measured neighborhood distances of the candidates. The gaps between these bounds are managed, to be reduced quickly after each level, resulting in an efficient filtering algorithm.

Its combination of early termination and low-cost refinement makes this strategy interesting. The analysis and experiments show the superiority of the strategy compared to conventional methods. It would be better if the authors explained in more detail how to apply the technique to distances other than Euclidean. I think the appendix could probably be made shorter by applying Cauchy’s inequality.