Approximate nearest neighbors beyond space partitions

We show improved data structures for the high-dimensional approximate nearest neighbor search problem (ANN) for ℓp distances for "large" values of p and for generalized Hamming distances. The previous best data structures proceeded by embedding a metric of interest into the ℓ∞ space or an ℓ∞-direct sum with simple summands, and then using data structures of Indyk (FOCS 1998, SoCG 2002) for ℓ∞-ANN. In contrast to this, we bypass the embedding step and proceed by extending the technique underlying the ℓ∞ data structures to handle ℓp and generalized Hamming distances directly. The resulting data structures are randomized, in contrast to Indyk's result for ℓ∞-ANN, and replicate input points, in contrast with Locality Sensitive Hashing. This leads to ANN data structures with significantly improved approximations over those implied by embeddings, as well as those obtained using all known approaches based on random space partitions.