Consistent Weighted Sampling

By Mark S. Manasse, Frank McSherry, Kunal Talwar. 2007

100 citations recorded by the source corpus.

Subfields: Information Retrieval & Search, Algorithms & Complexity

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Information Retrieval & Search

In Algorithms & Complexity

Citations in the corpus

Improved Consistent Sampling, Weighted Minhash and L1 Sketching (2010, methodology): “An extra advantage of our method compared to that of [10] is that for each feature and each hash we sample 3 random variables (r, c and β), independently of the input weight.”
Theory and applications of b-bit minwise hashing (2011, background): “Since the original minwise hashing work [2, 4], there have been considerable theoretical and methodological developments [3, 5, 13,15,17,18,22].”
Beyond Pairwise: Provably Fast Algorithms for Approximate k-Way Similarity Search (2013, result): “For example, our results naturally apply to consistent weighted sampling [25, 15], which is one way to handle non-binary sparse data.”
Asymmetric Minwise Hashing for Indexing Binary Inner Products and Set Containment (2015, methodology): “At this point, we can use existing methods for consistent weighted sampling [30, 23, 19, 26].”
Mechanism Design via Differential Privacy (2007, unknown): “The approach uses a generalization of min-wise independent sampling to non-uniform distributions, one implementation of which can be found in [29].”
UNICORN: Runtime Provenance-Based Detector for Advanced Persistent Threats (2020, methodology): “U NICORN employs HistoSketch [132], an approach based on consistent weighted sampling [82], that efﬁciently maintains compact and ﬁxed-size sketches for streaming histograms.”
Towards Sharp Inapproximability For Any 2-CSP (2007, unknown): “The approach uses a generalization of min-wise independent sampling to non-uniform distributions, one implementation of which can be found in [29].”
Consistent Weighted Sampling Made Fast, Small, and Easy (2014, methodology): “More recent papers [12, 19, 14] removed the integer weight restriction, and showed how to produce samples using a constant number of hash evaluations for any element, independent of its weight.”
Min-Max Kernels (2015, methodology): “The min-max kernel was sparsely discussed in the literature [24, 14].”
Asymmetric Minwise Hashing (2014, methodology): “At this point, we can use existing methods for consistent weighted sampling on the new data after asymmetric transformations [29, 22, 18].”