Hardness of Nearest Neighbor under L-infinity
Alexandr Andoni, Dorian Croitoru, Mihai Pǎtraşcu · 2008
Recent years have seen a significant increase in our understanding of high-dimensional nearest neighbor search (NNS) for distances like the lscr1and lscr2norms. By contrast, our understanding of the lscrinfinnorm is now where it was (exactly) 10 years ago. In FOCSpsila98, Indyk proved the following unorthodox result: there is a data structure (in fact, a decision tree) of size O(nrho), for any rho > 1, which achieves approximation O(logrholog d) for NNS in the d-dimensional lscr1metric. In this paper, we provide results that indicate that Indykpsilas unconventional bound might in fact be optimal. Specifically, we show a lower bound for the asymmetric communication complexity of NNS under lscrinfin, which proves that this space/approximation trade-off is optimal for decision trees and for data structures with constant cell-probe complexity.