Real time analytics using hybrid histograms
View Patent ↗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.
1. A system, comprising:
at least one computing device for processing a stream of data events by performing a method comprising:
providing 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;
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;
periodically recalculating the boundary values such that each percentile range includes a substantially similar number of associated counts; and
analyzing the hybrid histogram.
2. The system of claim 1 , wherein the identifying includes a binary tree algorithm.
3. The system of claim 1 , wherein the recalculating includes recalculating the boundary values periodically after a predefined plurality of data event values is processed.
4. The system of claim 1 , wherein the recalculating includes recalculating 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 relcalculating includes determining 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 relcalculating includes determining a new boundary B for the q'th boundary as:
B[q]=B[q]+K 2*( PR[q]−CC/N )
where K 2 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 relcalculating includes determining a new boundary B for the q'th boundary as:
B[q]=B[q]+K 3 [q ]*( PR[q]−CC/N ),
where CC is a cumulative count of events counted in the buckets below the boundary B and:
K 3 [q]=K 2*( 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 , the method further comprising defining a number of percentile ranges in the hybrid histogram and 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 analyzing includes selecting a process 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 storage 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]+K 2*( PR[q]−CC/N )
where K 2 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]+K 3 [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:
K 3 [q]=K 2*( B[r]−[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, on at least one computing device, 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, on the at least one computing device, a new data event value;
identifying, on the at least one computing device, a percentile range from the plurality of percentile ranges into which the new data event value falls;
incrementing, on the at least one computing device, the count associated with the identified percentile range;
periodically recalculating, on the at least one computing device, the boundary values such that each percentile range includes a substantially similar number of associated counts; and
analyzing, on the at least one computing device, 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, on the at least one computing device, a number of periodic ranges in the hybrid histogram and defining, on the at least one computing device, initial values for the boundary values.
26. The method of claim 21 , wherein analyzing the hybrid histogram includes selecting a process from the group consisting of: identifying potentially fraudulent activities, identifying trends and patterns, identifying risks, identifying problems, and identifying business opportunities.