Optimal Lower Bound for Itemset Frequency Indicator Sketches

Abstract

Given a database, a common problem is to find the pairs or $k$-tuples of items that frequently co-occur. One specific problem is to create a small space "sketch" of the data that records which $k$-tuples appear in more than an $\hat{I}\mu$ fraction of rows of the database. We improve the lower bound of Liberty, Mitzenmacher, and Thaler [LMT14], showing that $\hat{I}\text{c◯}(\frac{1}{\hat{I}}\mu d\log (\hat{I}\mu d))$ bits are necessary even in the case of $k=2$. This matches the sampling upper bound for all $\hat{I}\mu \ge 1/d^{.99}$, and (in the case of $k=2$) another trivial upper bound for $\hat{I}\mu =1/d$.

3 pages