  Sketch-based streaming algorithms allow efficient processing of big data.
These algorithms use small fixed-size storage to store a summary ("sketch") of
the input data, and use probabilistic algorithms to estimate the desired
quantity. However, in many real-world applications it is impractical to collect
and process the entire data stream, the common practice is thus to sample and
process only a small part of it. While sampling is crucial for handling massive
data sets, it may reduce accuracy. In this paper we present a new framework
that can accurately estimate the cardinality of any set expression between any
number of streams using only a small sample of each stream. The proposed
framework consists of a new sketch, called Maximal-Term with Subsample (MTS),
and a family of algorithms that use this sketch. An example of a possible query
that can be efficiently answered using the proposed sketch is, How many
distinct tuples appear in tables $T_1$ and $T_2$, but not in $T_3$? The
algorithms presented in this paper answer such queries accurately, processing
only a small sample of the tuples in each table and using a constant amount of
memory. Such estimations are useful for the optimization of queries over very
large database systems. We show that all our algorithms are unbiased, and we
analyze their asymptotic variance.
