Proceedings of the AAAI Conference on Artificial Intelligence · 2021 · 22 citations · 52 references
ComputingComputer ScienceData ScienceAlgorithmsData MiningMachine LearningHash TablesResampling MethodsResampling TechniquesSampling TheoryHashingJaccard SimilarityRejection SamplingSamplingSimilarity Detection
Efficiently computing the weighted Jaccard similarity has become an active research topic in machine learning and theory. For sparse data, the standard technique is based on the consistent weighed sampling (CWS). For dense data, however, methods based on rejection sampling (RS) can be much more efficient. Nevertheless, existing RS methods are still slow for practical purposes. In this paper, we propose to improve RS by a strategy, which we call efficient rejection sampling (ERS), based on ``early stopping + densification''. We analyze the statistical property of ERS and provide experimental results to compare ERS with RS and other algorithms for hashing weighted Jaccard. The results demonstrate that ERS significantly improves the existing methods for estimating the weighted Jaccard similarity in relatively dense data.
52
Similarity estimation techniques from rounding algorithms
Moses Charikar · 2002 · 2.2K citations
Nitin Jindal, Bing Liu · 2008 · 1.5K citations
Syntactic clustering of the Web
Andrei Broder, S. Glassman, Mark S. Manasse et al. · Computer Networks and ISDN Systems · 1997 · 1.4K citations