SYSTEM AND METHOD FOR PICK-AND-DROP SAMPLING

• US 20140149364A1
• Filed: 11/23/2012
• Published: 05/29/2014
• Est. Priority Date: 11/23/2012
• Status: Active Grant

• Current Assignee: Regents of the University of California (University of California)
• Original Assignee: Regents of the University of California (University of California)
• Inventors: Ostrovsky, Rafail, Braverman, Vladimir
• Granted Patent: US 9,158,822 B2
• Time in Patent Office: Days
• US Class Current: 707/692
• CPC Class Codes: G06F 16/2365 Ensuring data consistency and integrity
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries
• CPC Class Codes: G06F 16/2462 Approximate or statistical queries

Abstract

A database system includes an input to a database server configured to deliver a data stream formed of a sequence of elements, D={p₁, p₂, . . . , p_m} of size m of numbers from {1, . . . , n} to the database server. The system further includes a computer program that causes a processor to approximate frequency moments (F_k) in the data stream, such that a frequency of an element (i) is defined as f_i=|{j:p_j=i}| and a k-th frequency moment of D is defined as

$F_k=\sum _{i=1}^nm_i^k\mathrm{in}a$

single pass through the data stream. The processor is caused to carry out the steps of locating elements (i) with a frequency ΩF_k in the data stream as heavy elements and approximating f_i as ≧ a fraction of f_i to limit memory resources used by the processor to estimate F_k to O(n^1−2/k log(n)) bits.

Claims

1. A database system comprising:

a database;

a database server configured to control reading data from and writing data to the database;

an input to the database server configured to deliver a data stream formed of a sequence of elements, D={p₁, p₂, . . . , p_m} of size m of numbers from {1, . . . , n} to the database server;

a non-transitive, computer-readable storage medium, having stored thereon, a computer program that, when executed by a processor, causes the processor to approximate frequency moments (F_k) in the data stream, such that a frequency of an element (i) is defined as f_i=|{j;

p_j=i}| and a k-th frequency moment of D is defined as

2. The database system of claim 1 wherein the processor is further caused to implement a local counter to count a number of times an element appears in a suffix of a row in the matrix.

3. The database system of claim 2 wherein the processor is further caused to implement a global counter incremented as a function of the local counter.

4. The database system of claim 3 wherein the processor is further caused to drop and re-initiate the global counter if the local counter exceeds the global counter.

5. The database system of claim 1 wherein the processor is further caused to approximate f_i as ≧

a fraction of f_i to limit memory resources used by the processor to estimate F_k to O(n<sup>1−

2/k</sup> log(n)) bits.

6. A method for approximating frequency moments (F_k)) in data streams formed of a sequence of elements, D={p₁, p₂, . . . , p_m} of size m of numbers from {1, . . . , n}, such that a frequency of an element (i) is defined as f_i=|{j:

p_j=i}| and a k-th frequency moment of D is defined as

7. The method of claim 6 wherein further comprising implementing a local counter to count a number of times an element appears in a suffix of a row in the matrix.

8. The method of claim 7 further comprising implementing a global counter incremented as a function of the local counter.

9. The method of claim 8 further comprising dropping and re-initiating the global counter if the local counter exceeds the global counter.

10. The method of claim 6 further comprising approximating f_i as ≧

a fraction of f_i to limit memory resources used by the processor to estimate F_k to O(n<sup>1−

2/k</sup> log(n)) bits.

11. The method of claim 6 further comprising limiting a degree of frequency moment (k) to greater than 2.

12. A database system comprising:

a database;

a database server configured to control reading data from and writing data to the database;

an input to the database server configured to deliver a data stream formed of a sequence of elements, D={p₁, p₂, . . . , p_m} of size m of numbers from {1, . . . , n} to the database server;

a non-transitive, computer-readable storage medium, having stored thereon, a computer program that, when executed by a processor, causes the processor to approximate frequency moments (F_k)) in the data stream, such that a frequency of an element (i) is defined as f_i=|{j;

p_j=i}| and a k-th frequency moment of D is defined as

13. The database system of claim 12 wherein the processor is further caused to limit a degree of frequency moment (k) to greater than 2.

14. The database system of claim 12 wherein the processor is further caused to arranging a portion of the data stream in a matrix, select an initial element in the matrix, and check the matrix for a duplicate of the initial element.

15. The database system of claim 14 wherein the processor is further caused to, upon identifying a duplicate of the initial element in the matrix, assume that the initial element appears in each row of the matrix, assign binary values to all other frequencies, and disregard the initial element.

16. The database system of claim 14 wherein the processor is further caused to, upon completing checking the matrix without identifying a duplicate of the initial element, assign a binary value to all frequencies.

17. The database system of claim 14 wherein the processor is further caused to analyze each subsequent element in the matrix by checking the matrix for a duplicate of each subsequent element.

18. The database system of claim 12 wherein the processor is further caused to generate a report of approximated frequency moments in the data stream.