REAL TIME ANALYTICS USING HYBRID HISTOGRAMS

• US 20080140347A1
• Filed: 12/12/2006
• Published: 06/12/2008
• Est. Priority Date: 12/12/2006
• Status: Active Grant

• Current Assignee: LinkedIn Corporation (Microsoft Corporation)
• Original Assignee: International Business Machines Corporation
• Inventors: Selby, David A., Ramsey, Mark S., Todd, Stephen J.
• Granted Patent: US 7,826,663 B2
• Time in Patent Office: Days
• US Class Current: 702/180
• 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
• CPC Class Codes: G06Q 10/00 Administration; Management

Abstract

A system, method and program product for processing a stream of data events using hybrid histograms. A system is provided that includes: a hybrid histogram that provides a running statistical summary of the stream of data events, wherein the hybrid histogram includes a plurality of percentile ranges, a set of boundary values that separate the percentile ranges, and a count associated with each of the percentile ranges; a histogram processing system for identifying a percentile range from the plurality of percentile ranges into which a new data event value falls, and for incrementing the count associated with the identified percentile range; a periodic boundary recalculation system for periodically recalculating the boundary values such that each percentile range includes a substantially similar number of associated counts; and an analysis system that analyzes the hybrid histogram.

Claims

1. A system for processing a stream of data events, comprising:

a hybrid histogram that provides a running statistical summary of the stream of data events, wherein the hybrid histogram includes a plurality of percentile ranges, a set of boundary values that separate the percentile ranges, and a count associated with each of the percentile ranges;

a histogram processing system for identifying a percentile range from the plurality of percentile ranges into which a new data event value falls, and for incrementing the count associated with the identified percentile range;

a boundary recalculation system for periodically recalculating the boundary values such that each percentile range includes a substantially similar number of associated counts; and

an analysis system that analyzes the hybrid histogram.

2. The system of claim 1, wherein the histogram processing system includes a binary tree algorithm.

3. The system of claim 1, wherein the boundary recalculation system recalculates the boundary values periodically after a predefined plurality of data event values is processed.

4. The system of claim 1, wherein the boundary recalculation system recalculates the boundary values using a data-driven analysis in which a new boundary is calculated when a number of counts for a bucket exceed a balanced size by more than a predetermined amount.

5. The system of claim 1, wherein the boundary recalculation system determines a new boundary B for a q'"'"'th bucket as:

B[q]=B[q]+K*(N*PR[q]−

CC)

where K is an adjustment constant, CC is a cumulative count of events counted in the buckets below the boundary B, and PR[q] is a percentile range boundary for the q'"'"'th bucket.

6. The system of claim 1, wherein the boundary recalculation system determines a new boundary B for the q'"'"'th boundary as:

B[q]=B[q]+K2*(PR[q]−

CC/N)

where K2 is an adjustment constant, CC is a cumulative count of events counted in the buckets below the boundary B, and PR[q] is a percentile range boundary for the q'"'"'th bucket.

7. The system of claim 4, wherein the boundary recalculation system determines a new boundary B for the q'"'"'th boundary as:

B[q]=B[q]+K3[q]*(PR[q]−

CC/N),

where CC is a cumulative count of events counted in the buckets below the boundary B and;

K3[q]=K2*(B[r]−

B[l])/(PR[r]−

PR[l])

where B[r] is a boundary value immediately to the left of B, B[l] is a boundary value immediately to the right of B, PR[r] is a percentile range boundary immediately to the right of B and PR[l] is a percentile range boundary immediately to the left of B.

8. The system of claim 1, further comprising a histogram definition system for defining a number of percentile ranges in the hybrid histogram and for defining initial values for the boundary values.

9. The system of claim 1, wherein the stream of data events come from a source selected from the group consisting of:

a financial institution, a network, a device, a computer program, a business, and an enterprise.

10. The system of claim 1, wherein the analysis system includes a process selected from the group consisting of:

identifying potentially fraudulent activities, identifying trends and patterns, identifying risks, identifying problems, and identifying business opportunities.

11. A computer program product stored on a computer readable medium, which when executed, processes a stream of data events, the program product comprising:

computer program code configured for updating a hybrid histogram data object that stores a running statistical summary of the stream of data events, wherein the hybrid histogram data object includes a plurality of percentile ranges, a set of boundary values that separate the percentile ranges, and a count associated with each of the percentile ranges;

computer program code configured for identifying a percentile range from the plurality of percentile ranges into which a new data event value falls, and for incrementing the count associated with the identified percentile range;

computer program code configured for periodically recalculating the boundary values such that each percentile range includes a substantially similar number of associated counts; and

computer program code configured for analyzing the hybrid histogram data object.

12. The program product of claim 11, wherein the computer program code configured for identifying a percentile range includes a binary tree algorithm.

13. The program product of claim 11, wherein the computer program code configured for periodically recalculating the boundary values periodically recalculates the boundary values after a predefined plurality of data event values is processed.

14. The program product of claim 11, wherein the computer program code configured for periodically recalculating the boundary values recalculates the boundary values using a data-driven analysis in which a new boundary is calculated when a number of counts for a bucket exceed a balanced size by more than a predetermined amount.

15. The program product of claim 11, wherein the computer program code configured for periodically recalculating the boundary values determines a new boundary B for the q'"'"'th boundary as:

B[q]=B[q]+K*(N*PR[q]−

CC)

where K is an adjustment constant, CC is a cumulative count of events counted in the buckets below the boundary B, and PR is a percentile range.

16. The program product of claim 11, wherein the computer program code configured for periodically recalculating the boundary values determines a new boundary B for the q'"'"'th boundary as:

B[q]=B[q]+K2*(PR[q]−

CC/N)

where K2 is an adjustment constant, CC is a cumulative count of events counted in the buckets below the boundary B, and PR is a percentile range.

17. The program product of claim 11, wherein the computer program code configured for periodically recalculating the boundary values determines a new boundary B for the q'"'"'th boundary as:

B[q]=B[q]+K3[q]*(PR[q]−

CC/N),

where CC is a cumulative count of events counted in the buckets below the boundary B, PR[q] is a percentile range for the qth bucket and;

K3[q]=K2*(B[r]−

B[l])/(PR[r]−

PR[l])

where B[r] is a boundary value immediately to the left of B, B[l] is a boundary value immediately to the right of B, PR[r] is a percentile range immediately to the right of B and PR[l] is a percentile range immediately to the left of B.

18. The program product of claim 11, further comprising computer program code configured for defining a number of percentile ranges in the hybrid histogram data object and for defining initial values for the boundary values.

19. The program product of claim 11, wherein the stream of data events come from a source selected from the group consisting of:

a financial institution, a network, a device, a computer program, a business, and an enterprise.

20. The program product of claim 11, wherein the computer program code configured for analyzing the hybrid histogram data object includes a process selected from the group consisting of:

identifying potentially fraudulent activities, identifying trends and patterns, identifying risks, identifying problems, and identifying business opportunities.

21. A method of processing a stream of data events, comprising:

providing a hybrid histogram that stores a running statistical summary of the stream of data events, wherein the hybrid histogram includes a plurality of percentile ranges, a set of boundary values that separate the percentile ranges, and a count associated with each of the percentile ranges;

obtaining a new data event value;

identifying a percentile range from the plurality of percentile ranges into which the new data event value falls;

incrementing the count associated with the identified percentile range;

periodically recalculating the boundary values such that each percentile range includes a substantially similar number of associated counts; and

analyzing the hybrid histogram.

22. The method of claim 21, wherein identifying the percentile range includes using a binary tree algorithm.

23. The method of claim 21, wherein periodically recalculating occurs after a predefined plurality of data event values is processed.

24. The method of claim 21, wherein recalculating occurs when a number of counts for a bucket exceeds a balanced size.

25. The method of claim 21, further comprising defining a number of periodic ranges in the hybrid histogram and defining initial values for the boundary values.

26. The method of claim 21, wherein analyzing the hybrid histogram includes a process selected from the group consisting of:

identifying potentially fraudulent activities, identifying trends and patterns, identifying risks, identifying problems, and identifying business opportunities.