Decimation of fixed length queues

• US 20040003149A1
• Filed: 06/26/2002
• Published: 01/01/2004
• Est. Priority Date: 06/26/2002
• Status: Abandoned Application

• Current Assignee: Agilent Technologies, Inc.
• Original Assignee: Agilent Technologies, Inc.
• Inventors: Hamilton, Bruce, Engel, Glenn R.
• Application Number:
  US10/180,801
• Publication Number:
  US 20040003149A1
• Time in Patent Office: Days
• US Class Current: 710/54
• CPC Class Codes: G06F 5/14 for overflow or underflow handling, e.g. full or empty flags

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.

Claims

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.