Patent ID: 8738618

Claim:
A method comprising: using one or more processors to execute instructions retained in one or more machine-readable media to perform operations comprising: accessing a plurality of bottom-k sketches summarizing a plurality of sets (denoted herein by S) over a collection of items, the plurality of sets (S) associated with a query having a predicate for the plurality of sets over the collection of items, a first one of the bottom-k sketches (denoted herein by s k (A,r)) for a first one of the sets (denoted herein by A, which represents a set in S) including pairs of ranks and weights for a subset of the items, the ranks being determined according to a rank assignment (denoted herein by r), the subset containing a first number (denoted herein by k) of the items having smallest ranks among the items included in the first one of the sets (A), the first one of the bottom-k sketches (s k (A,r)) also including a next largest rank (denoted herein by r k+1 (A)) corresponding to a smallest remaining rank among the remaining items included in the first one of the sets (A) but not included in the first one of the bottom-k sketches (s k (A,r)); selecting a plurality of available items of a combination of the plurality of bottom-k sketches based on determining that the predicate is an attribute-based selection, the combination (denoted herein by (SCS k (S,r)) of the plurality of bottom-k sketches (s k (A,r) for AεS) containing more than the first number (k) of the items contained in each one of the plurality of bottom-k sketches (s k (A,r) for AεS) and including any item from the plurality of bottom-k sketches (s k (A,r) for AεS) having a respective rank less than a limiting rank (denoted herein by r k+1 (S)), the limiting rank (r k+1 (S)) being a minimum of a plurality of next largest ranks (r k+1 (A) for AεS) corresponding respectively to the plurality of bottom-k sketches (s k (A,r) for AεS); identifying a plurality of identified items among the plurality of available items, the plurality of identified items satisfying the predicate; assigning a first adjusted weight to a first item of the plurality of identified items based on a weight of the first item and a distribution associated with the plurality of bottom-k sketches; and generating an estimate based on the first adjusted weight assigned to the first item and adjusted weights assigned to other identified items from the combination of the plurality of bottom-k sketches and that satisfy the predicate.