Please use this identifier to cite or link to this item: https://doi.org/10.1109/ICDM.2013.119
Title: Min-max hash for jaccard similarity
Authors: Ji, J.
Li, J.
Yan, S. 
Tian, Q.
Zhang, B.
Keywords: approximate nearest neighbor search
Jaccard similarity
min-max hash
min-wise hash
Issue Date: 2013
Citation: Ji, J., Li, J., Yan, S., Tian, Q., Zhang, B. (2013). Min-max hash for jaccard similarity. Proceedings - IEEE International Conference on Data Mining, ICDM : 301-309. ScholarBank@NUS Repository. https://doi.org/10.1109/ICDM.2013.119
Abstract: Min-wise hash is a widely-used hashing method for scalable similarity search in terms of Jaccard similarity, while in practice it is necessary to compute many such hash functions for certain precision, leading to expensive computational cost. In this paper, we introduce an effective method, i.e. the min-max hash method, which significantly reduces the hashing time by half, yet it has a provably slightly smaller variance in estimating pair wise Jaccard similarity. In addition, the estimator of min-max hash only contains pair wise equality checking, thus it is especially suitable for approximate nearest neighbor search. Since min-max hash is equally simple as min-wise hash, many extensions based on min-wise hash can be easily adapted to min-max hash, and we show how to combine it with b-bit minwise hash. Experiments show that with the same length of hash code, min-max hash reduces the hashing time to half as much as that of min-wise hash, while achieving smaller mean squared error (MSE) in estimating pair wise Jaccard similarity, and better best approximate ratio (BAR) in approximate nearest neighbor search. © 2013 IEEE.
Source Title: Proceedings - IEEE International Conference on Data Mining, ICDM
URI: http://scholarbank.nus.edu.sg/handle/10635/83960
ISSN: 15504786
DOI: 10.1109/ICDM.2013.119
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

7
checked on Sep 17, 2018

WEB OF SCIENCETM
Citations

6
checked on Sep 17, 2018

Page view(s)

43
checked on Jul 20, 2018

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.