Answers are grounded in this paper and cite their sources.
Analyses space complexity in constructing itemset-frequency sketches, indicating polynomials bound it rather than exponentials.
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.
No takes yet. Share an insight, caveat, or question.
Yamamoto Yoshitaka (2026) studied this question.
Synapse has enriched 8 closely related papers on similar clinical questions. Consider them for comparative context: