This paper, "Graphical Model Sketch," was presented by researchers from Adobe Research, Rutgers University, and TTI Chicago. It introduces a novel way to estimate probabilities in massive, complex data streams by marrying the structural strengths of graphical models with the space efficiency of data sketches.
TL;DR
Estimating probabilities in high-cardinality data streams (like millions of unique web URLs) is traditionally a choice between massive memory usage or high error rates. This paper introduces "Graphical Model Sketches," which use the structure of a Bayesian network to decompose joint probabilities into smaller, "sketchable" factors, providing accurate estimates with memory requirements independent of the data's cardinality.
What Problem Does This Paper Address?
In fields like online advertising or Natural Language Processing (NLP), we often need to estimate the probability of specific events—for example, "What is the likelihood a user from San Jose visits a specific product page after clicking a specific ad?"
There are two main challenges here:
- High Cardinality ($M$): Variables like "User Location" or "Page URL" can have millions of unique values. A standard joint probability table for just two such variables would require trillions of entries ($M^2$), making it impossible to store in RAM.
- High Dimensionality ($K$): When you have many variables, the "curse of dimensionality" kicks in. Standard tools like the Count-Min (CM) sketch—a popular "frequency table" that uses hashing to save space—don't scale well. To estimate the joint probability of 10 variables, a CM sketch would either need an astronomical amount of memory or produce errors so large they render the estimate useless.
Methods
The authors propose a hybrid approach. They take a Graphical Model (specifically a Bayesian network), which describes how variables depend on one another, and "sketch" its individual components.
Instead of trying to sketch the entire joint distribution $P(X_1, ..., X_K)$ as one giant variable, they use the chain rule of probability to break it down into a product of smaller conditional probabilities (factors), such as $P(X_{child} | X_{parent})$.
They analyze three specific algorithms:
- GMHash: The simplest version, using basic hash tables to estimate ratios.
- GMSketch: An improvement that uses the "median trick" (taking the median of multiple independent estimates) to boost reliability.
- GMFactorSketch: Their flagship algorithm. It estimates each conditional probability factor as a ratio of two separate Count-Min sketches.
The key innovation is that the space complexity of these sketches is independent of the cardinality $M$. It only depends on the number of variables ($K$) and the desired accuracy.
Datasets
The researchers evaluated their algorithms using two primary sources:
- Synthetic Naive Bayes Model: A controlled environment with 32 variables, each with a cardinality of $2^{16}$ (65,536 values). This allowed them to test "heavy" (frequent) and "light" (rare) events.
- Adobe Marketing Cloud Data: A real-world dataset consisting of 65 million page views. Each view was described by six high-cardinality variables: Country, City, Page Name, Starting Page Name, Campaign, and Browser. The "Page Name" variable alone contained over 42,000 unique values.
Key Insights and Ideas
- Structure as a Compressor: By assuming a graphical structure (like a tree), the authors effectively "pre-compress" the problem. The sketch only needs to handle the dependencies defined by the graph edges, rather than every possible combination of variables.
- Multiplicative Error vs. Additive Error: Standard CM sketches usually provide additive error bounds (e.g., "the estimate is off by $\pm 0.01$"). For rare events with probabilities like $0.00001$, additive error is useless. Graphical Model Sketches provide multiplicative error bounds, meaning the error is proportional to the actual value, making it much more effective for "long-tail" data.
- The "Hardness" Constant ($\Delta$): The authors identified a query-specific constant, $\Delta(x)$, which represents the minimum probability of any variable-parent pair in the query. They proved that the space required is inversely proportional to this constant, showing that very rare co-occurrences are intrinsically harder to sketch.
Key Results
- Order of Magnitude Improvement: In both synthetic and real-world tests, GMFactorSketch outperformed the standard CM sketch by a massive margin. For the same amount of memory, GMFactorSketch was significantly more likely to provide a "precise" estimate (defined as being within a factor of $e$ of the true value).
- Space Efficiency: On the Adobe dataset, the CM sketch failed to provide useful estimates until it was given a very large amount of space. In contrast, the Graphical Model Sketches achieved high accuracy with a fraction of that memory.
- Theoretical Optimality: The authors provided a lower bound proof showing that their dependence on the "hardness" of the query is order-optimal—meaning you likely can't do much better without using more space.
Limitations and Future Work
- Known Structure: The current algorithms assume the structure of the graphical model (the "map" of which variables depend on which) is known beforehand. In many streaming scenarios, you might not know the structure and would need to learn it on the fly.
- Point Queries Only: The paper focuses on "point queries"—estimating the probability of one specific outcome. It does not yet address more complex "marginal queries" (e.g., "What is the probability of $X_1$ regardless of what $X_2$ is?").
- Tree Assumption: While the math can be extended, the exposition and most of the analysis focus on tree-structured graphs. Extending this efficiently to graphs with many loops (high treewidth) remains a challenge for future research.
Summary updated