worst Zipf Zipf Uniq Uniq 0.1% 1.0% 27K 9K 6K 419 27K 1K 0.05% 0.5% 58K 17K 11K 709 58K 2K 0.01% 0.1% 322K 69K 37K 2K 322K 10K 0.005% 0.05% 672K 124K 62K 4K 672K 20K Table 1: Memory requirements in terms [...] tuples. 1.1 Motivating Examples Here are four problems drawn from databases, data min- ing, and computer networks, where frequency counts ex- ceeding a user-specified threshold are computed. 1. An iceberg [...] threshold . A prototypical query on a re- lation R(c1, c2, , ck, rest) with threshold is SELECT c1, c2, , ck, COUNT(rest) FROM R GROUP BY c1, c2, , ck HAVING COUNT(rest) The parameter is equivalent …