Dynamic data stream histograms for large ranges

• US 20070282888A1
• Filed: 05/31/2006
• Published: 12/06/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, Lopez, Alejandro Pablo
• Granted Patent: US 7,702,699 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 17/18 for evaluating statistical data , e.g. average values, frequency distributions, probability functions, regression analysis forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04

Abstract

A method for creating a histogram from a plurality of data elements that includes specifying a plurality of internal buckets, wherein each internal bucket of the plurality of internal buckets represent values between an internal minimum value and an internal maximum value, wherein a plurality of differences of the internal minimum value and the internal maximum value of each internal bucket are heterogeneous, populating the plurality of internal buckets with the plurality of data elements based on the internal minimum value and the internal maximum value of each internal bucket to obtain a plurality of populated internal buckets, and outputting the histogram from the plurality of populated internal buckets.

Claims

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

specifying a plurality of internal buckets, wherein each internal bucket of the plurality of internal buckets represent values between an internal minimum value and an internal maximum value, wherein a plurality of differences of the internal minimum value and the internal maximum value of each internal bucket are heterogeneous;

populating the plurality of internal buckets with the plurality of data elements based on the internal minimum value and the internal maximum value of each internal bucket to obtain a plurality of populated internal buckets; and

outputting the histogram from the plurality of populated internal buckets.

2. The method of claim 1, wherein each of the plurality of internal buckets comprises a counter.

3. The method of claim 2, wherein populating the plurality of internal buckets comprises:

identifying an internal bucket in the plurality of internal buckets according to the internal minimum value and the internal maximum value of the internal bucket for each of the plurality of data elements; and

incrementing the counter associated with the internal bucket.

4. The method of claim 1, further comprising:

receiving the plurality of data elements continually from a network,

wherein the plurality of internal buckets are populated 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 data elements;

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

calculating a starting internal bucket of the plurality of internal buckets and an ending internal bucket of the plurality of internal buckets for each of a plurality of external buckets from the range; and

summing a counter for a subset of the plurality of internal buckets between the starting internal bucket and ending internal bucket for each of the plurality of external buckets to create a total for each of the plurality of external buckets;

outputting the total for each of the plurality of external buckets.

6. The method of claim 5, wherein the maximum value and the minimum value is determined from a parameter in a command to create the histogram.

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

identifying a number of the plurality of external buckets, wherein the starting internal bucket and ending internal bucket is calculated using the number of the plurality of external buckets and the range.

8. The method of claim 5, wherein the number of the plurality of external buckets is determined from a parameter in a command to create the histogram.

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

a plurality of internal buckets, wherein each internal bucket of the plurality of internal buckets represent values between an internal minimum value and an internal maximum value, wherein a plurality of differences of the internal minimum value and the internal maximum value of each internal bucket are heterogeneous; and

a histogram engine configured to;

populate the plurality of internal buckets with the plurality of data elements based on the internal minimum value and the internal maximum value of each internal bucket to obtain a plurality of populated internal buckets; and

output the histogram from the plurality of populated internal buckets.

10. The system of claim 9, wherein each of the plurality of internal buckets comprises a counter.

11. The system of claim 10, wherein populating the plurality of internal buckets comprises:

identifying an internal bucket in the plurality of internal buckets according to the scope represented by the internal bucket for each of the plurality of data elements; and

incrementing the counter associated with the internal bucket.

12. The system of claim 9, wherein the histogram engine is further configured to:

receive the plurality of data elements continually from a network,

wherein the plurality of internal buckets are populated while the plurality of data elements are received.

13. The system of claim 9, wherein creating the histogram comprises:

identifying a minimum value and a maximum value for the plurality of data elements;

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

calculating a starting internal bucket of the plurality of internal buckets and an ending internal bucket of the plurality of internal buckets for each of a plurality of external buckets using the range; and

summing a counter for a subset of the plurality of internal buckets between the starting internal bucket and ending internal bucket for each of the plurality of external buckets to create a total for each of the plurality of external buckets;

outputting the total for each of the plurality of external buckets.

14. The system of claim 13, wherein the maximum value and the minimum value is determined from a parameter in a command to create the histogram.

15. The system of claim 13, creating the histogram further comprises:

identifying a number of the plurality of external buckets, wherein the starting internal bucket and ending internal bucket is calculated using the number of the plurality of external buckets and the range.

16. The system of claim 13, wherein the number of the plurality of external buckets is determined from a parameter in a command to create the histogram.

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

specify a plurality of internal buckets, wherein each internal bucket of the plurality of internal buckets represent values between an internal minimum value and an internal maximum value, wherein a plurality of differences of the internal minimum value and the internal maximum value of each internal bucket are heterogeneous;

populate the plurality of internal buckets with the plurality of data elements based on the internal minimum value and the internal maximum value of each internal bucket to obtain a plurality of populated internal buckets; and

output a histogram from the plurality of populated internal buckets.

18. The computer usable medium of claim 17, wherein populating the plurality of internal buckets comprises:

identifying a internal bucket in the plurality of internal buckets according to the scope represented by the internal bucket for each of the plurality of data elements; and

incrementing a counter associated with the internal bucket.

19. The computer usable medium of claim 17, wherein creating the histogram comprises:

identifying a minimum value and a maximum value for the plurality of data elements;

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

calculating a starting internal bucket of the plurality of internal buckets and an ending internal bucket of the plurality of internal buckets for each of a plurality of external buckets from the range; and

summing a counter for a subset of the plurality of internal buckets between the starting internal bucket and ending internal bucket for each of the plurality of external buckets to create a total for each of the plurality of external buckets;

outputting the total for each of the plurality of external buckets.

20. The computer usable medium of claim 19, wherein creating the histogram further comprises:

identifying a number of the plurality of external buckets, wherein the starting internal bucket and ending internal bucket is calculated using the number of the plurality of external buckets and the range.