Please use this identifier to cite or link to this item:
|Title:||Min-max hash for jaccard similarity||Authors:||Ji, J.
|Keywords:||approximate nearest neighbor search
|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.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.