Dynamic data stream histograms for no loss of information

• US 20070288205A1
• Filed: 05/31/2006
• Published: 12/13/2007
• Est. Priority Date: 05/31/2006
• Status: Active Grant

• Current Assignee: Oracle America, Inc. (Oracle Corporation)
• Original Assignee: Sun Microsystems Incorporated (Oracle Corporation)
• Inventors: Vazquez, Pedro, Chenede, Erwann
• Granted Patent: US 7,430,494 B2
• Time in Patent Office: Days
• US Class Current: 702/189
• CPC Class Codes: G06Q 10/04 Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem" market predictions or forecasting for commercial activities G06Q30/0202

Abstract

A method for creating a histogram from a plurality of data elements that includes identifying a lower extreme range counter and an upper extreme range counter for the plurality of data elements, incrementing a value counter when the value counter corresponds to a value of a first data element in the plurality of data elements, incrementing the lower extreme range counter, wherein incrementing the lower extreme range counter is performed when a value of a second data element in the plurality of data elements is less than a pre-defined lower boundary, incrementing the upper extreme range counter, wherein incrementing the upper extreme range counter is performed when a value of a third data element in the plurality of data elements is greater than a pre-defined upper boundary, and creating the histogram from the value counter, the lower extreme range counter, and the upper extreme range counter.

Claims

1. A method for creating a histogram from a plurality of data elements comprising:

identifying a lower extreme range counter and an upper extreme range counter for the plurality of data elements;

incrementing a value counter when the value counter corresponds to a value of a first data element in the plurality of data elements;

incrementing the lower extreme range counter, wherein incrementing the lower extreme range counter is performed when a value of a second data element in the plurality of data elements is less than a pre-defined lower boundary;

incrementing the upper extreme range counter, wherein incrementing the upper extreme range counter is performed when a value of a third data element in the plurality of data elements is greater than a pre-defined upper boundary; and

creating the histogram from the value counter, the lower extreme range counter, and the upper extreme range counter.

2. The method of claim 1, wherein identifying the lower extreme range counter and the upper extreme range counter for the plurality of data elements comprises:

receiving a plurality of initialization values; and

assigning the pre-defined lower boundary and the predefined upper boundary from the plurality of initialization values.

3. The method of claim 2, wherein assigning the pre-defined lower boundary and the pre-defined upper boundary for the plurality of initialization values comprises:

calculating the pre-defined lower boundary using a percentage,

wherein the percentage of the plurality of initialization values are less than the lower boundary; and

calculating the pre-defined upper boundary using the percentage,

wherein the percentage of the plurality of initialization values are greater than the upper boundary.

4. The method of claim 1, further comprising:

receiving the plurality of data elements continually from a network,

wherein the plurality of counters are incremented while the plurality of data elements are received.

5. The method of claim 1, wherein creating the histogram comprises:

identifying a minimum value and a maximum value for the plurality of counters;

calculating a range according to the minimum value and the maximum value;

calculating a starting value counter of the plurality of value counters and an ending value counter of the plurality of value counters for each of a plurality of buckets from the range;

summing a subset of the plurality of value counters for each of the plurality of buckets to create a total for each of the plurality of buckets, wherein the subset of the plurality of value counters are between the starting value counter and ending value counter; and

outputting the total for each of the plurality of buckets.

6. The method of claim 5, wherein the maximum value and the minimum value are determined by parameters passed when creating the histogram.

7. The method of claim 5, wherein creating the histogram further comprises:

identifying a pre-defined number of the plurality of buckets, wherein the starting value counter and ending value counter is calculated using the pre-defined number of the plurality of buckets and the range.

8. The method of claim 7, wherein the pre-defined number of the plurality of buckets is determined by a parameter passed when creating the histogram.

9. The method of claim 5, wherein creating the histogram further comprises:

outputting the lower extreme range counter and the upper extreme range counter.

10. A system for creating a histogram from a plurality of data elements comprising:

a data repository for storing a value counter, a lower extreme range counter, and an upper extreme range counter; and

a histogram engine configured to;

identify the lower extreme range counter and the upper extreme range counter for the plurality of data elements;

increment the value counter when the value counter corresponds to a value of a first data element in the plurality of data elements;

increment the lower extreme range counter, wherein incrementing the lower extreme range counter is performed when a value of a second data element in the plurality of data elements is less than a pre-defined lower boundary;

increment the upper extreme range counter, wherein incrementing the upper extreme range counter is performed when a value of a third data element in the plurality of data elements is greater than a pre-defined upper boundary; and

create the histogram from the value counter, the lower extreme range counter, and the upper extreme range counter.

11. The system of claim 10, wherein identifying the lower extreme range counter and the upper extreme range counter for the plurality of data elements comprises:

receiving a plurality of initialization values; and

assigning the pre-defined lower boundary and the pre-defined upper boundary from the plurality of initialization values.

12. The system of claim 11, wherein assigning the pre-defined lower boundary and the pre-defined upper boundary for the plurality of initialization values comprises:

calculating the pre-defined lower boundary using a percentage,

wherein the percentage of the plurality of initialization values are less than the lower boundary; and

calculating the pre-defined upper boundary using the percentage,

wherein the percentage of the plurality of initialization values are greater than the upper boundary.

13. The system of claim 10, wherein the histogram engine is further configured to:

receiving the plurality of data elements continually from a network,

wherein the plurality of counters are incremented while the plurality of data elements are received.

14. The system of claim 10, wherein creating the histogram comprises:

identifying a minimum value and a maximum value for the plurality of counters;

calculating a range according to the minimum value and the maximum value;

calculating a starting value counter of the plurality of value counters and an ending value counter of the plurality of value counters for each of a plurality of buckets from the range;

summing a subset of the plurality of value counters for each of the plurality of buckets to create a total for each of the plurality of buckets, wherein the subset of the plurality of value counters are between the starting value counter and ending value counter; and

outputting the total for each of the plurality of buckets.

15. The system of claim 14, wherein the maximum value and the minimum value are determined by parameters passed when creating the histogram.

16. The system of claim 14, wherein creating the histogram further comprises:

identifying a pre-defined number of the plurality of buckets, wherein the starting value counter and ending value counter is calculated using the pre-defined number of the plurality of buckets and the range.

17. The system of claim 16, wherein the pre-defined number of the plurality of buckets is determined by a parameter passed when creating the histogram.

18. The system of claim 14, wherein creating the histogram further comprises:

outputting the lower extreme range counter and the upper extreme range counter.

19. A computer usable medium comprising computer readable program code embodied therein for causing a computer system to:

identify a lower extreme range counter and an upper extreme range counter for a plurality of data elements;

increment a value counter when the value counter corresponds to a value of a first data element in the plurality of data elements;

increment the lower extreme range counter, wherein incrementing the lower extreme range counter is performed when a value of a second data element in the plurality of data elements is less than a pre-defined lower boundary;

increment the upper extreme range counter, wherein incrementing the upper extreme range counter is performed when a value of a third data element in the plurality of data elements is greater than a pre-defined upper boundary; and

create a histogram from the value counter, the lower extreme range counter, and the upper extreme range counter.

20. The computer usable medium of claim 19, wherein identifying the lower extreme range counter and the upper extreme range counter for the plurality of data elements comprises:

receiving a plurality of initialization values; and

assigning the pre-defined lower boundary and the predefined upper boundary from the plurality of initialization values.