System and method for pick-and-drop sampling

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 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 method for approximating frequency moments (F k ) in 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 
                     t 
                     k 
                   
                 
               
               , 
             
           
         
       
       the method comprising 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 each subsequent element in the matrix; and 
 (g) generating a report of approximated heavy elements in the data stream. 
 
     
     
         2 . The method of  claim 1  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. 
     
     
         3 . The method of  claim 2  further comprising implementing a global counter incremented as a function of the local counter. 
     
     
         4 . The method of  claim 3  further comprising dropping and re-initiating the global counter if the local counter exceeds the global counter. 
     
     
         5 . The method of  claim 1  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. 
     
     
         6 . The method of  claim 1  further comprising limiting a degree of frequency moment (k) to greater than 2. 
     
     
         7 . 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 
                   t 
                   k 
                 
               
             
           
         
       
       in a single pass through the data stream by:
   locating elements (i) with a frequency ΩF k  in the data stream as heavy elements;   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.   
 
     
     
         8 . The database system of  claim 7  wherein the processor is further caused to limit a degree of frequency moment (k) to greater than 2. 
     
     
         9 . The database system of  claim 7  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. 
     
     
         10 . The database system of  claim 9  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. 
     
     
         11 . The database system of  claim 9  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. 
     
     
         12 . The database system of  claim 9  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. 
     
     
         13 . The database system of  claim 7  wherein the processor is further caused to generate a report of approximated frequency moments in the data stream.