Techniques are provided for improving the speed and accuracy of analytics on big data using theta sketches, by converting fixed-size sketches to theta sketches, and by performing set operations on sketches. In a technique for performing a set operation, two sketches are analyzed to identify the maximum value of each sketch. The maximum values of the two sketches are compared. Based the comparison, one or more values are removed from the sketch whose maximum value is greater. After the removal, a set operation (e.g., union, intersection, or difference) is performed based on the modified sketch and the unmodified sketch. A result of the set operation is a third sketch, which may be used to estimate a cardinality of the larger data sets that are represented by the two input sketches.