Hardness of Nearest Neighbor under L-infinity

Recent years have seen a significant increase in our understanding of high-dimensional nearest neighbor search (NNS) for distances like the l(1) and l(2) norms. By contrast, our understanding of the l(infinity) norm is now where it was (exactly) 10 years ago. In FOCS'98, Indyk proved the following unorthodox result: there is a data structure (in fact, a decision tree) of size O(n(rho)), for any rho > 1, which achieves approximation O(log(rho) log d) for NNS in the d-dimensional l(infinity) metric. In this paper we provide results that indicate that Indyk's unconventional bound might in fact be optimal. Specifically, we show a lower bound for the asymmetric communication complexity of NNS under l(infinity), which proves that this space/approximation trade-off is optimal for decision trees and for data structures with constant cell-probe complexity.