SYSTEM AND METHOD FOR PICK-AND-DROP SAMPLING

摘要

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$$ ;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.