System and method for pick-and-drop sampling
View Patent ↗A database system includes an input to a database server configured to deliver a data stream formed of a sequence of elements, D={p 1 , p 2 , . . . , 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 = ∑ i = 1 n m i k 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.
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 1 , p 2 , . . . , 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
F
k
=
∑
i
=
1
n
m
i
k
in a single pass through the data stream by the steps of:
(a) arranging a portion of the data stream in a matrix;
(b) selecting an initial element in the matrix;
(c) checking the matrix for a duplicate of the initial element;
(d) upon identifying a duplicate of the initial element in the matrix, assuming that the initial element appears in each row of the matrix, assigning binary values to all other frequencies, and disregarding the initial element;
(e) upon completing step (c) without identifying a duplicate of the initial element, assigning a binary value to all frequencies;
(f) repeating steps (b) through (e) for a each subsequent element in the matrix; and
(g) generating a report of approximated frequency moments in the data stream.
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 1−2/k log(n)) bits.
6. A method for approximating frequency moments (Fk) in data streams, the method comprising the steps of:
(a) arranging a portion of the data stream in a matrix, the data streams formed of a sequence of elements, D ={p 1 , p 2 , . . . , 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
f
(
k
)
=
∑
i
=
1
n
m
i
k
;
(b) selecting an initial element in the matrix;
(c) checking the matrix for a duplicate of the initial element;
(d) upon identifying a duplicate of the initial element in the matrix, assuming that the initial element appears in each row of the matrix, assigning binary values to all other frequencies, and disregarding the initial element;
(e) upon completing step (c) without identifying a duplicate of the initial element, assigning a binary value to all frequencies;
(f) repeating steps (b) through (e) for each subsequent element in the matrix; and
(g) generating a report of approximated heavy elements in the data stream.
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 1−2/k log(n)) bits.
11. The method of claim 6 further comprising limiting a degree of frequency moment (k) to greater than 2.
12. A
non-transitive, computer-readable storage medium, comprising:
a computer program stored on the non-transitive, computer-readable storage medium 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
f
(
k
)
=
∑
i
=
1
n
m
i
k
in a single pass through the data stream by:
(a) arranging a portion of the data stream in a matrix;
(b) selecting an initial element in the matrix;
(c) checking the matrix for a duplicate of the initial element;
(d) upon identifying a duplicate of the initial element in the matrix, assuming that the initial element appears in each row of the matrix, assigning binary values to all other frequencies, and disregarding the initial element;
(e) upon completing step (c) without identifying a duplicate of the initial element, assigning a binary value to all frequencies;
(f) repeating steps (b) through (e) for a each subsequent element in the matrix: and
(g) generating a report of approximated frequency moments in the data stream.
13. The non-transitive, computer-readable storage medium of claim 12 wherein the processor is further caused to limit a degree of frequency moment (k) to greater than 2.