Densifying One Permutation Hashing via Rotation for Fast Near Neighbor Search

Abstract

The query complexity of locality sensitive hash-ing (LSH) based similarity search is dominated by the number of hash evaluations, and this num-ber grows with the data size (Indyk & Motwani, 1998). In industrial applications such as search where the data are often high-dimensional and binary (e.g., text n-grams), minwise hashing is widely adopted, which requires applying a large number of permutations on the data. This is costly in computation and energy-consumption. In this paper, we propose a hashing technique which generates all the necessary hash evalu-ations needed for similarity search, using one single permutation. The heart of the proposed hash function is a “rotation ” scheme which den-sifies the sparse sketches of one permutation hashing (Li et al., 2012) in an unbiased fash-ion thereby maintaining the LSH property. This makes the obtained sketches suitable for hash ta-ble construction. This idea of rotation presented in this paper could be of independent interest for densifying other types of sparse sketches. Using our proposed hashing method, the query time of a (K,L)-parameterized LSH is reduced from the typical O(dKL) complexity to merely O(KL + dL), where d is the number of nonze-ros of the data vector,K is the number of hashes in each hash table, and L is the number of hash tables. Our experimental evaluation on real data confirms that the proposed scheme significantly reduces the query processing time over minwise hashing without loss in retrieval accuracies. 1.