SYSTEMS AND METHODS FOR CORRELATION OF BURST EVENTS AMONG DATA STREAMS

• US 20090086755A1
• Filed: 07/22/2008
• Published: 04/02/2009
• Est. Priority Date: 09/30/2005
• Status: Active Grant

• Current Assignee: GlobalFoundries, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Wu, Kun-Lung, Vlachos, Michail, Chen, Shyh-Kwei, Yu, Philip Shi-lung
• Granted Patent: US 7,961,631 B2
• Time in Patent Office: Days
• US Class Current: 370/468
• 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
• CPC Class Codes: G06Q 40/00 Finance; Insurance; Tax strategies; Processing of corporate or income taxes
• CPC Class Codes: G06Q 50/00 Information and communication technology [ICT] specially adapted for implementation of business processes of specific business sectors, e.g. utilities or tourism healthcare informatics G16H
• CPC Class Codes: H04L 41/064 involving time analysis
• CPC Class Codes: H04L 43/0894 Packet rate

Abstract

Systems and methods for the identification of correlated burst events among two or more data streams, given one or more specific query time spans are disclosed. Also broadly contemplated is the act of finding, from one or more data streams, those streams that have correlated burst events with another given data stream within a time span.

Claims

1. A method of correlating burst events among two or more data streams, said method comprising the steps of:

identifying burst features;

maintaining and updating a burst feature index;

searching the burst feature index; and

identifying correlated data streams that exhibit burst events within one or more predetermined query time spans.

2. The method according to claim 1, wherein said step of maintaining and updating a burst feature index comprises maintaining and updating a burst feature index on-the-fly.

3. The method according to claim 1, wherein said step of maintaining and updating a burst feature index comprises representing burst features as burst time intervals.

4. The method according to claim 3, wherein said step of identifying burst features comprises identifying burst intervals via imposing at least one threshold on data in the data streams.

5. The method according to claim 1, wherein said step of identifying correlated data streams comprises estimating a degree of correlation between burst features via calculating one or more time overlaps of burst features.

6. The method according to claim 5, wherein said calculating step comprises calculating one or more time overlaps of burst features via employing an index.

7. The method according to claim 6, wherein said step of employing an index feature comprises employing a Containment-Encoded-Interval Index.

8. The method according to claim 1, wherein said step of maintaining and updating a burst feature index comprises maintaining an array of burst interval ID lists.

9. The method according to claim 8, wherein said step of maintaining an array of burst interval ID lists comprises:

defining two or more layers of grid intervals;

decomposing each burst interval with one or more grid intervals; and

inserting a burst interval ID into burst interval ID lists associated with the one or more grid intervals.

10. The method according to claim 1, wherein said searching step comprises:

finding entire grid intervals that overlap with one or more predetermined query time spans; and

finding entire burst interval IDs stored in burst interval ID lists associated with found overlapping grid intervals.

11. The method according to claim 10, wherein said step of finding entire grid intervals comprises:

finding entire unit-sized grid intervals that are completely covered by the query span; and

finding entire ancestor grid intervals for unit-sized grid intervals so found.

12. The method according to claim 10, wherein said step of finding entire grid intervals comprises, with a given query time span:

for each layer of grid intervals, finding a leftmost and a rightmost grid interval overlapping with the query time span; and

applying numerals between the leftmost and rightmost grid intervals via successively incrementing the grid interval ID by 1.

13. A computer system for correlating burst events among two or more data streams, said system comprising:

a module for identifying burst features;

a module for maintaining and updating a burst feature index;

a module for searching the burst feature index; and

a module for identifying correlated data streams that exhibit burst events within one or more predetermined query time spans.

14. The system according to claim 13, wherein said module for maintaining and updating a burst feature index acts to maintain and update a burst feature index on-the-fly.

15. The system according to claim 13, wherein:

said module for maintaining and updating a burst feature index acts to represent burst features as burst time intervals; and

said module for identifying burst features acts to identify burst intervals via imposing at least one threshold on data in the data streams.

16. The system according to claim 13, wherein:

said module for identifying correlated data streams acts to estimate a degree of correlation between burst features via calculating one or more time overlaps of burst features via employing an index.

17. The system according to claim 16, wherein said module for identifying correlated data streams acts to employ a Containment-Encoded-Interval Index in calculating one or more time overlaps of burst features.

18. The system according to claim 13, wherein said module for maintaining and updating a burst feature index acts to maintain an array of burst interval ID lists via:

defining two or more layers of grid intervals;

decomposing each burst interval with one or more grid intervals; and

inserting a burst interval ID into burst interval ID lists associated with the one or more grid intervals.

19. The system according to claim 13, wherein said searching module acts to:

find entire grid intervals that overlap with one or more predetermined query time spans; and

find entire burst interval IDs stored in burst interval ID lists associated with found overlapping grid intervals.

20. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for correlating burst events among two or more data streams, said method comprising the steps of:

identifying burst features;

maintaining and updating a burst feature index;

searching the burst feature index; and

identifying correlated data streams that exhibit burst events within one or more predetermined query time spans.