%0 Conference Paper %1 LiSK12 %A Li, Ping %A Shrivastava, Anshumali %A König, Arnd Christian %B Proceedings of the 21st World Wide Web Conference (WWW 2012) (Companion Volume) %D 2012 %K imported %P 565-566 %R 10.1145/2187980.2188129 %T GPU-based minwise hashing: GPU-based minwise hashing %U http://doi.acm.org/10.1145/2187980.2188129 %X Minwise hashing is a standard technique for efficient set similarity estimation in the context of search. The recent work of b-bit minwise hashing provided a substantial improvement by storing only the lowest b bits of each hashed value. Both minwise hashing and b-bit minwise hashing require an expensive preprocessing step for applying k (e.g., k=500) permutations on the entire data in order to compute k minimal values as the hashed data. In this paper, we developed a parallelization scheme using GPUs, which reduced the processing time by a factor of 20-80. Reducing the preprocessing time is highly beneficial in practice, for example, for duplicate web page detection (where minwise hashing is a major step in the crawling pipeline) or for increasing the testing speed of online classifiers (when the test data are not preprocessed).

@inproceedings{LiSK12, abstract = {Minwise hashing is a standard technique for efficient set similarity estimation in the context of search. The recent work of b-bit minwise hashing provided a substantial improvement by storing only the lowest b bits of each hashed value. Both minwise hashing and b-bit minwise hashing require an expensive preprocessing step for applying k (e.g., k=500) permutations on the entire data in order to compute k minimal values as the hashed data. In this paper, we developed a parallelization scheme using GPUs, which reduced the processing time by a factor of 20-80. Reducing the preprocessing time is highly beneficial in practice, for example, for duplicate web page detection (where minwise hashing is a major step in the crawling pipeline) or for increasing the testing speed of online classifiers (when the test data are not preprocessed).}, added-at = {2015-01-19T16:50:57.000+0100}, author = {Li, Ping and Shrivastava, Anshumali and K{\"o}nig, Arnd Christian}, bibsource = {DBLP, http://dblp.uni-trier.de}, biburl = {https://www.bibsonomy.org/bibtex/25276b16af1ed1cf1c65f41e32cf53e04/ncrn-cornell}, booktitle = {Proceedings of the 21st World Wide Web Conference (WWW 2012) (Companion Volume)}, doi = {10.1145/2187980.2188129}, interhash = {9bbb6a320a455ace0f7606fa3067eb77}, intrahash = {5276b16af1ed1cf1c65f41e32cf53e04}, keywords = {imported}, pages = {565-566}, timestamp = {2015-01-19T16:50:57.000+0100}, title = {GPU-based minwise hashing: GPU-based minwise hashing}, url = {http://doi.acm.org/10.1145/2187980.2188129}, year = 2012 }