Unbiased space-saving data sketches for estimating disaggregated subset sums and estimating frequent items

1. A method of data sketching, comprising:

at a computer system having one or more processors and memory storing one or more programs configured for execution by the one or more processors:

selecting a plurality of data fields from a data source having a plurality of data rows;

determining a number N of bins for aggregating rows of the data source;

allocating storage in the memory for N bins, each bin comprising storage space for a key value and an associated counter value, with the associated counter value initialized to zero; and

sequentially processing the plurality of rows in the data source, including;

for each row, computing a respective key value for the respective row using data values for the selected plurality of data fields in the respective row, the plurality of rows including at least a first subset, a second subset, and a third subset;

for each row in the first subset of the plurality of rows:

determining that the respective key value matches a key value for a respective first bin; and

incrementing the counter value for the respective first bin;

for each row in the second subset of the plurality of rows:

determining that the respective key value does not match any bin key value and that there exists one or more bins having a counter value of zero;

selecting a respective second bin having a counter value of zero;

setting the key value of the respective second bin to be the respective key value; and

setting the counter value of the respective second bin to be one; and

for each row in the third subset of the plurality of rows:

determining that the respective key value does not match any bin key value and that all of the N bins have non-zero counter values;

identifying a respective third bin with a smallest counter value c;

incrementing the counter value of the respective third bin; and

with probability 1/(1+c), replacing the key value of the respective third bin with the respective key value, including:

generating a respective pseudorandom number in a first range, the first range including a subrange corresponding to the probability 1/(1+c):

in accordance with a determination that the respective pseudorandom number is within the subrange, replacing the key value of the respective third bin with the respective key value for the respective row; and

in accordance with a determination that the respective pseudorandom number is outside the subrange, retaining the key value of the respective third bin.

2. The method of claim 1 , wherein the data source is streaming.

3. The method of claim 1 , further comprising:

receiving a query from a client to identify M frequent items from the N bins, wherein M is a positive integer less than N;

in response to receiving the query:

selecting, from the N bins, M bins having the largest counter values; and

returning the key values of the selected M bins to the client.

4. The method of claim 1 , further comprising:

receiving a query from a client to estimate a count of rows from the data source satisfying a user-specified filter condition;

in response to receiving the query:

determining a subset of the bins whose key values satisfy the user-specified filter condition;

computing a sum of the counter values for the bins in the determined subset; and

returning, to the client, the sum as an estimate of the count of rows from the data source satisfying the filter condition.

5. The method of claim 1 , wherein determining the number N of bins for aggregating rows of the data source comprises:

receiving user specification of an error limit e for estimating subset sums for the data set;

receiving a user estimate P of a fraction of the rows in the data set that will satisfy expected subset sum filters; and

selecting the number N to be a positive integer satisfying

N

≥

1

P

⁢

⁢

ɛ

2

.

6. The method of claim 1 , wherein the selected data fields are f 1 , f 2 , . . . , f k , and computing the respective key value for the respective row comprises forming a concatenation f 1 (r)+f 2 (r)+ . . . +f k (r), where f i (r) specifies the f i data field value for the row r for i=1, 2, . . . , k, and f i (r) casts the corresponding data field value as a string when the data type of the data field f i is not a string.

7. The method of claim 1 , wherein the selected data fields are f 1 , f 2 , . . . , f k , and computing the respective key value for the respective row comprises forming a k-tuple (f 1 (r), f 2 (r), . . . , f k (r)), where f i (r) specifies the f i data field value for the row r for i=1, 2, . . . , k.

8. The method of claim 1 , wherein each bin further comprises storage space for a hash of the bin key value, and matching a respective key value to a key value for a respective bin comprises:

computing a respective hash value of the respective key value; and

comparing the respective hash value to bin hash values.

9. The method of claim 1 , further comprising partitioning data values for a first data field, of the selected plurality of data fields, into a plurality of distinct partitions, each partition consisting of a respective list or range of data values;

wherein matching the respective key value to a respective bin value comprises:

identifying the data values of the first data field in the respective key value and in the respective bin key value, and determining that the identified data values are in a same partition.

10. A computer system having one or more computing devices, each computing device having one or more processors and memory, wherein the memory stores one or more programs configured for execution by the one or more processors, and the one or more programs comprise instructions for:

selecting a plurality of data fields from a data source having a plurality of data rows;

determining a number N of bins for aggregating rows of the data source;

allocating storage in the memory for N bins, each bin comprising storage space for a key value and an associated counter value, with the associated counter value initialized to zero; and

sequentially processing the plurality of rows in the data source, including:

for each row, computing a respective key value for the respective row using data values for the selected plurality of data fields in the respective row, the plurality of rows including at least a first subset, a second subset, and a third subset;

for each row in the first subset of the plurality of rows:

determining that the respective key value matches a key value for a respective first bin; and

incrementing the counter value for the respective first bin;

for each row in the second subset of the plurality of rows:

determining that the respective key value does not match any bin key value and that there exists one or more bins having a counter value of zero;

selecting a respective second bin having a counter value of zero;

setting the key value of the respective second bin to be the respective key value; and

setting the counter value of the respective second bin to be one; and

for each row in the third subset of the plurality of rows:

determining that the respective key value does not match any bin key value and that all of the N bins have non-zero counter values;

identifying a respective third bin with a smallest counter value c;

incrementing the counter value of the respective third bin; and

with probability 1/(1+c), replacing the key value of the respective third bin with the respective key value, including:

generating a respective pseudorandom number in a first range, the first range including a subrange corresponding to the probability 1/(1+c):

in accordance with a determination that the respective pseudorandom number is within the subrange, replacing the key value of the respective third bin with the respective key value for the respective row; and

in accordance with a determination that the respective pseudorandom number is outside the subrange, retaining the key value of the respective third bin.

11. The computer system of claim 10 , wherein the data source is streaming.

12. The computer system of claim 10 , wherein the one or more programs further comprise instructions for:

receiving a query from a client to identify M frequent items from the N bins, wherein M is a positive integer less than N;

in response to receiving the query:

selecting, from the N bins, M bins having the largest counter values; and

returning the key values of the selected M bins to the client.

13. The computer system of claim 10 , wherein the one or more programs further comprise instructions for:

receiving a query from a client to estimate a count of rows from the data source satisfying a user-specified filter condition;

in response to receiving the query:

determining a subset of the bins whose key values satisfy the user-specified filter condition;

computing a sum of the counter values for the bins in the determined subset; and

returning, to the client, the sum as an estimate of the count of rows from the data source satisfying the filter condition.

14. The computer system of claim 10 , wherein determining the number N of bins for aggregating rows of the data source comprises:

receiving user specification of an error limit e for estimating subset sums for the data set;

receiving a user estimate P of a fraction of the rows in the data set that will satisfy expected subset sum filters; and

selecting the number N to be a positive integer satisfying

N

≥

1

P

⁢

⁢

ɛ

2

.

15. The computer system of claim 10 , wherein the selected data fields are f 1 , f 2 . . . , f k , and computing the respective key value for the respective row comprises forming a concatenation f 1 (r)+f 2 (r)+ . . . +f k (r), where f i (r) specifies the f i data field value for the row r for i=1, 2, . . . , k, and f i (r) casts the corresponding data field value as a string when the data type of the data field f i is not a string.

16. The computer system of claim 10 , wherein the selected data fields are f 1 , f 2 , . . . f k , and computing the respective key value for the respective row comprises forming a k-tuple (f 1 (r), f 2 (r), . . . , f k (r)), where f i (r) specifies the f i data field value for the row r for i=1, 2, . . . , k.

17. The computer system of claim 10 , wherein each bin further comprises storage space for a hash of the bin key value, and matching a respective key value to a key value for a respective bin comprises:

computing a respective hash value of the respective key value; and

comparing the respective hash value to bin hash values.

18. The computer system of claim 10 , wherein the one or more programs further comprise instructions for partitioning data values for a first data field, of the selected plurality of data fields, into a plurality of distinct partitions, each partition consisting of a respective list or range of data values;

wherein matching the respective key value to a respective bin value comprises:

identifying the data values of the first data field in the respective key value and in the respective bin key value, and determining that the identified data values are in a same partition.

19. A method of data sketching, comprising:

at a computer system having one or more processors and memory storing one or more programs configured for execution by the one or more processors:

selecting a plurality of data fields from a data source having a plurality of data rows and selecting a summation data field, having a numeric data type, from the data source;

determining a number N of bins for aggregating rows of the data source;

allocating storage in the memory for N bins, each bin comprising storage space for a key value and an associated magnitude, with the associated magnitude initialized to zero; and

sequentially processing the plurality of rows in the data source, including:

for each row, computing a respective key value for the respective row using data values for the selected plurality of data fields in the respective row, and identifying a respective summation value s comprising a data value for the summation data field in the respective row, the plurality of rows including at least a first subset, a second subset, and a third subset;

for each row in the first subset of the plurality of rows:

determining that the respective key value matches a key value for a respective first bin; and

adding the respective summation value to the magnitude for the respective bin;

for each row in the second subset of the plurality of rows:

determining that the respective key value does not match any bin key value and there exists one or more bins having a magnitude of zero,

selecting a respective second bin having a magnitude of zero;

setting the key value of the respective second bin to be the respective key value; and

setting the magnitude of the respective second bin to be the respective summation value;

for each row in the third subset of the plurality of rows:

determining that the respective key value does not match any bin key value and that all of the N bins have non-zero magnitudes;

identifying a respective third bin with a smallest magnitude c;

adding the respective summation value to the magnitude of the respective third bin; and

with probability s/(s+c), replacing the key value of the respective third bin with the respective key value, including:

generating a respective pseudorandom number in a first range, the first range including a subrange corresponding to the probability s/(s+c):

in accordance with a determination that the respective pseudorandom number is within the subrange, replacing the key value of the respective third bin with the respective key value for the respective row; and

in accordance with a determination that the respective pseudorandom number is outside the subrange, retaining the key value of the respective third bin.

20. The method of claim 19 , wherein each bin further comprises storage space for a hash of the bin key value, and matching a respective key value to a key value for a respective bin comprises:

computing a respective hash value of the respective key value; and

comparing the respective hash value to bin hash values.