Locality-preserving hashing in multidimensional spaces

We consider locality-preserving hashing --- in which adjacent points in the domain are mapped to adjacent or nearlyadjacent points in the range --- when the domain is a d- dimensional cube. This problem has applications to highdimensional search and multimedia indexing. We show that simple and natural classes of hash functions are provably good for this problem. We complement this with lower bounds suggesting that our results are essentially the best possible. 1 Introduction In a recent paper, Linial and Sasson 21 proved the following theorem about hash functions: Theorem 1 There exists a family G of functions from an integer line 1; : : : ; U to 1; : : : ; R and a constant C such that for any S ae 1; : : : ; U with jSj C p R: ffl Prf2G(f jS is one to one) 1 2 ffl all f 2 G are non-expansive, i.e., for any p; q 2 U d(f(p);f(q)) d(p; q). The family G contains O(jU j) functions, each of which is computable in O(1) operations. Their result gives a family of hash fu...