A Sketch Algorithm for Estimating Two-Way and Multi-Way Associations

By Ping Li, Kenneth Ward Church. 2007

56 citations recorded by the source corpus.

We should not have to look at the entire corpus (e.g., the Web) to know if two (or more) words are strongly associated or not. One can often obtain estimates of associations from a small sample. We develop a sketch-based algorithm that constructs a contingency table for a sample. One can estimate the contingency table for the entire population using straightforward scaling. However, one can do better by taking advantage of the margins (also known as document frequencies). The proposed method cuts the errors roughly in half over Broder's sketches.

Subfields: Artificial Intelligence, Information Systems, Statistics and Probability, Algorithms & Complexity, Signal Processing

How researchers see this paper

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

In Artificial Intelligence

In Information Systems

In Statistics and Probability

In Algorithms & Complexity

In Signal Processing

Citations in the corpus

Asymmetric Minwise Hashing (2014, background): “Another potentially promising topic for future work might be asymmetric minwise hashing for 3-way (or higher-order) similarities [25, 34]”
Beyond Pairwise: Provably Fast Algorithms for Approximate k-Way Similarity Search (2013, methodology): “CRS performs very well for certain applications but it does not work in our context because the bottom (nonzero) subsets are not properly aligned.”
b-Bit Minwise Hashing for Estimating Three-Way Similarities (2010, background): “However, the analysis for developing the b-bit version of CRS appears to be very difficult.”
Theory and applications of b-bit minwise hashing (2011, methodology): “A related approach is Conditional Random Sampling (CRS) [17, 18] which uses only a single permutation and instead of a single minimum retains as set of the smallest hashed values.”
Hashing for Similarity Search: A Survey (2014, background): “Conditional random sampling [68], [67] also takes the k smallest nonzeros from one permutation, and is shown to be a more accurate similarity estimator.”