Decimation of fixed length queues

Abstract

Decimation of data from a fixed length queue retaining a representative sample of the old data. Exponential decimation removes every nth sample. Dithered exponential decimation offsets the exponential decimation approach by a probabilistic amount. Recursive decimation selects a portion of the queue and removes elements.

We claim:  
     
         1 . The method of removing elements from a fixed-length queue, the method comprising decimation of elements from the queue.  
     
     
         2 . The method of  claim 1  where the decimation method comprises exponential decimation.  
     
     
         3 . The method of  claim 2  where exponential decimation is applied to remove multiple elements from the queue.  
     
     
         4 . The method of  claim 2  where exponential decimation is applied to remove a single element from the queue.  
     
     
         5 . The method of  claim 1  where the decimation method comprises exponential decimation with dithering.  
     
     
         6 . The method of  claim 1  where the decimation method comprises recursive decimation, recursively selecting a portion of the queue and removing a randomly chosen element.  
     
     
         7 . The method of  claim 6  where separate random numbers are used for each removal of an element from the selected portion of the queue.  
     
     
         8 . The method of  claim 6  where a single random number is generated for the recursive decimation process, each step of the process using only as many bits of the random number as needed.  
     
     
         9 . The method of  claim 6  where recursive decimation is applied to remove multiple elements from the queue.  
     
     
         10 . The method of  claim 6  where recursive decimation is applied to remove a single element from the queue.  
     
     
         11 . An article of manufacture for performing decimation of a fixed length queue, the article of manufacture comprising: 
 at least one computer readable medium;    processor instructions contained on the computer readable medium, the instructions configured to be readable by at least one processor and to cause the processor to remove elements from a fixed length queue by decimation.    
     
     
         12 . The article of  claim 11 , where the decimation method comprises exponential decimation.  
     
     
         13 . The article of  claim 11  where the decimation method comprises exponential decimation with dithering.  
     
     
         14 . The article of  claim 11  where the decimation method comprises recursive decimation, recursively selecting a portion of the queue and removing a randomly chosen element.  
     
     
         15 . The article of  claim 11  where the decimation method removes multiple elements from the queue.  
     
     
         16 . The article of  claim 11  where the decimation method removes a single element from the queue.  
     
     
         17 . The article of  claim 14  where separate random numbers are used for each removal of an element from the selected portion of the queue.  
     
     
         18 . The article of  claim 14  where a single random number is generated for the recursive decimation process, each step of the process using only as many bits of the random number as needed.