On the Space Complexity of Deterministic Online Algorithms for Constructing Itemset-Frequency Sketches

We consider the deterministic online construction of Itemset-Frequency Sketches over binary transaction streams. The central question is whether the space complexity required for approximate frequency responses inherently depends on the combinatorial explosion 2^l of the number of itemsets, or whether it can be bounded by a polynomial in the number of items l. We provide an online construction based on discrepancy theory and ε-approximation, and then analyse the error blow-up arising from the successive increase in the number of items, modelled as εl = εl−1 + δl. Through symmetrisation, reduction to an α/δ lower- bound problem, two-layer witnesses, and the analysis of the resulting recurrence, we establish εl = O(ε1 l^8). This result implies that the space complexity of deterministic online Itemset-Frequency Sketches can be evaluated as a polynomial in l rather than an exponential in l.