Decimation of fixed length queues

• US 20060075163A1
• Filed: 12/06/2005
• Published: 04/06/2006
• Est. Priority Date: 06/26/2002
• Status: Active Grant

• Current Assignee: Bruce Hamilton, Glenn R. Engel
• Original Assignee: Bruce Hamilton, Glenn R. Engel
• Inventors: Hamilton, Bruce, Engel, Glenn R.
• Granted Patent: US 7,330,917 B2
• Time in Patent Office: Days
• US Class Current: 710/52
• 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. (canceled)

2. (canceled)

3. (canceled)

4. (canceled)

5. (canceled)

6. (canceled)

7. (canceled)

8. (canceled)

9. (canceled)

10. (canceled)

11. (canceled)

12. (canceled)

13. (canceled)

14. (canceled)

15. (canceled)

16. (canceled)

17. (canceled)

18. (canceled)

19. A method of replacing elements of a single fixed-length queue, the method comprising exponentially decimating an element from the queue to create space for a new element, and inserting a new element into the created space.

20. A method as in claim 19 and further comprising shifting the created space toward an end of the queue before inserting the new element.

21. A method as in claim 19 wherein exponentially decimating comprises removing a plurality of elements from the queue to create a plurality of spaces for new elements, and wherein inserting a new element comprises inserting new elements into the created spaces.

22. A method as in claim 19 wherein exponentially decimating comprises dithering to select the element to be decimated.

23. A method of replacing elements of a single fixed-length queue, the method comprising recursively selecting a portion of the queue, randomly selecting an element in the selected portion, removing the selected element to create space for a new element, and inserting a new element into the created space.

24. A method as in claim 23 and further comprising repeating the foregoing steps.

25. A method as in claim 24 wherein randomly selecting an element comprises generating a pseudorandom number and using the generated number to select an element.

26. A method as in claim 23 wherein randomly selecting an element comprises generating a pseudorandom number and using a first part of the generated number to select an element.

27. A method as in claim 26 and further comprising recursively selecting a second portion of the queue, using a second part of the generated number to select an element in the second portion of the queue, removing the selected element to create space for a new element, and inserting a new element into the created space.

28. A method as in claim 23 and further comprising shifting the created space toward an end of the queue before inserting the new element.

29. An article of manufacture for replacing elements of a single fixed-length queue comprising a computer readable medium and processor instructions contained on the computer readable medium, the instructions configured to be readable by a processor and to cause the processor to decimate an element from the queue to create space for a new element and to insert a new element into the created space.

30. An article of manufacture as in claim 29 wherein the instructions cause the processor to shift the created space toward an end of the queue before inserting the new element.

31. An article of manufacture as in claim 29 wherein decimate comprises exponentially decimate.

32. An article of manufacture as in claim 31 wherein exponentially decimate comprises remove a plurality of elements from the queue to create a plurality of spaces for new elements, and wherein to insert a new element comprises to insert new elements into the created spaces.

33. An article of manufacture as in claim 31 wherein exponentially decimate comprises dither to select the element to be decimated.

34. An article of manufacture as in claim 29 wherein decimate comprises recursively select a portion of the queue, randomly select an element in the selected portion, remove the selected element to create space for a new element, and insert a new element into the created space.

35. An article of manufacture as in claim 34 wherein decimate further comprises recursively select another portion of the queue, randomly select an element in the selected portion, remove the selected element to create space for a new element, and insert a new element into the created space.

36. An article of manufacture as in claim 34 wherein randomly select an element comprises generate a pseudorandom number and use the generated number to select an element.

37. An article of manufacture as in claim 34 wherein randomly select an element comprises generate a pseudorandom number and use a first part of the generated number to select an element.

38. An article of manufacture as in claim 37 wherein randomly select an element further comprises recursively select a second portion of the queue, use a second part of the generated number to select an element in the second portion of the queue, remove the selected element to create space for a new element, and insert a new element into the created space.