Optimal Lower Bound for Itemset Frequency Indicator Sketches

الأصل · EN

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 ε fraction of rows of the database. We improve the lower bound of Liberty, Mitzenmacher, and Thaler [LMT14], showing that Ω(1εd (εd)) bits are necessary even in the case of k=2. This matches the sampling upper bound for all ε≥ 1/d.⁹⁹, and (in the case of k=2) another trivial upper bound for ε= 1/d.