Promise pruning can reduce search space nearly exponentially.
Pruning plays an integral role in reducing the search space of nearest neighbor queries on data structures like the R-tree. Often pruning strategies are defined for single nearest neighbor queries, and the generalization to k-nearest neighbor queries is left as an obvious extension. We show that one such pruning strategy, while predominantly thought only helpful in depth-first single nearest neighbor queries, when suitably generalized, results in a theoretically better search. In fact, it potentially reduces the search space nearly exponentially. We call this generalization promise pruning, provide empirical results exhibiting its success on both random and real-world data, and construct a class of R-trees where it reduces the search space from O(n) to O(log2 n).
Last modified 16 September 2002