  A data warehouse cannot materialize all possible views, hence we must
estimate quickly, accurately, and reliably the size of views to determine the
best candidates for materialization. Many available techniques for view-size
estimation make particular statistical assumptions and their error can be
large. Comparatively, unassuming probabilistic techniques are slower, but they
estimate accurately and reliability very large view sizes using little memory.
We compare five unassuming hashing-based view-size estimation techniques
including Stochastic Probabilistic Counting and LogLog Probabilistic Counting.
Our experiments show that only Generalized Counting, Gibbons-Tirthapura, and
Adaptive Counting provide universally tight estimates irrespective of the size
of the view; of those, only Adaptive Counting remains constantly fast as we
increase the memory budget.
