Decimation of fixed length queues having a number of position for holding data wherein new data is favored over old data

• US 7,330,917 B2
• Filed: 12/06/2005
• Issued: 02/12/2008
• Est. Priority Date: 06/26/2002
• Status: Expired due to Fees

• Current Assignee: Agilent Technologies, Inc.
• Original Assignee: Agilent Technologies, Inc.
• Inventors: Engel, Glenn R, Hamilton, Bruce
• Primary Examiner(s): PEYTON, TAMMARA R
• Application Number:
  US11/295,015
• Publication Number:
  US 20060075163A1
• Time in Patent Office: 798 Days
• Field of Search: 710/1, 710/20, 710/30, 710/35, 710/52, 710/65, 710/54, 712/225, 712/34, 711/126, 711/219
• 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. A method of managing a fixed-length queue having a number of positions for holding data items, the method comprising:

as the queue becomes filled with data items one or more times, creating in the queue a distribution of data items that exponentially favors new data items over old data items, and which includes at least one old data item and one new data item, by

decimating data items stored in different ones of the positions of the queue, to create spaces for new data items in the queue; and

inserting the new data items in the created spaces.

2. A method as in claim 1, wherein said decimating comprises exponentially decimating.

3. A method as in claim 1, wherein said decimating comprises recursively decimating, by,

recursively selecting a portion of the queue;

randomly selecting a data item in each selected portion of the queue;

decimating each randomly selected data item to create spaces for new data items in the queue; and

inserting the new data items in the created spaces.

4. A method as in claim 2, further comprising shifting the created spaces toward an end of the queue before inserting the new data items.

5. A method as in claim 2, wherein exponentially decimating comprises removing a plurality of elements from the queue, each time the queue becomes filled with data items, to create a plurality of spaces for the new data items.

6. A method as in claim 2, wherein exponentially decimating comprises dithering to select the data items to be decimated.

7. A method as in claim 3, further comprising repeating the steps for recursively decimating.

8. A method as in claim 7, wherein randomly selecting data item comprises generating a pseudorandom number and using the generated pseudorandom number to select data item.

9. A method as in claim 3, wherein randomly selecting data item in a first portion of the queue comprises generating a pseudorandom number and using a first part of the generated pseudorandom number to select data item in the first portion of the queue.

10. A method as in claim 9, wherein randomly selecting a data item in a second portion of the queue comprises using a second part of the generated pseudorandom number to select data item in the second portion of the queue.

11. A method as in claim 3, further comprising shifting the created spaces toward an end of the queue before inserting the new data items.

12. An article of manufacture, comprising:

at least one computer readable medium; and

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, as a fixed-length queue having a number of positions for holding data items becomes filled with data items one or more times, create in the queue a distribution of data items that exponentially favors new data items over old data items, and which includes at least one old data item and at least one new data item, by

decimating data items stored in different ones of the positions of the queue, to create spaces for new data items in the queue; and

inserting the new data items in the created spaces.

13. An article of manufacture as in claim 12, wherein the instructions cause the at least one processor to shift the created spaces toward an end of the queue before inserting the new data items.

14. An article of manufacture as in claim 12, wherein decimating comprises exponentially decimating.

15. An article of manufacture as in claim 14, wherein exponentially decimating comprises dithering to select the data items to be decimated.

16. An article of manufacture as in claim 12, wherein decimating comprises:

recursively selecting a portion of the queue;

randomly selecting a data item in each selected portion of the queue;

decimating each randomly selected data item to create spaces for new data items in the queue; and

a inserting new data items in the created spaces.

17. An article of manufacture as in claim 16, wherein randomly selecting a data item comprises generating a pseudorandom number and using the generated pseudorandom number to select data item.

18. An article of manufacture as in claim 16, wherein randomly selecting a data item comprises generating a pseudorandom number and using a first part of the generated pseudorandom number to select data item in the first portion of the queue.

19. An article of manufacture as in claim 18, wherein randomly selecting a data item in a second portion of the queue comprises using a second part of the generated pseudorandom number to select data item in the second portion of the queue.