Method and Apparatus for Maintaining and Processing Provenance Data in Data Stream Processing System

• US 20090292729A1
• Filed: 05/22/2008
• Published: 11/26/2009
• Est. Priority Date: 05/22/2008
• Status: Active Grant

• Current Assignee: International Business Machines Corporation, National Research Foundation Of Korea
• Original Assignee: Korea Evaluation Institute of Industrial Technology (Government of South Korea)
• Inventors: Sow, Daby Mousse, Wang, Min, Misra, Archan, Davis, John Sidney II, Blount, Marion Lee, Ebling, Maria Rene
• Granted Patent: US 8,301,626 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06N 5/042 Backward inferencing
• CPC Class Codes: G16H 50/20 for computer-aided diagnosis, e.g. based on medical expert systems

Abstract

Techniques are disclosed for maintaining and processing provenance data in such data stream processing systems. For example, a method for processing data associated with a data stream received by a data stream processing system, wherein the system comprises a plurality of processing elements, comprising the following steps. A portion of data associated with the data stream is maintained. The maintained data comprises inputs to each processing element that contributed to an output of each processing element. In response to an alert generated by one of the processing elements, a scheduler is triggered to determine when a pre-calculation of a prospective query related to the alert should be executed. In response to the scheduler, at least a portion of the maintained data is used to determine a set of data that contributed to the alert such that the alert-contributing set of data can be used to respond to the prospective query upon arrival thereof.

Claims

1. A method for processing data associated with a data stream received by a data stream processing system, wherein the system comprises a plurality of processing elements, the method comprising the steps of:

maintaining a portion of data associated with the data stream, wherein the maintained data comprises inputs to each processing element that contributed to an output of each processing element;

in response to an alert generated by one of the processing elements, triggering a scheduler to determine when a pre-calculation of a prospective query related to the alert should be executed; and

in response to the scheduler, using at least a portion of the maintained data to determine a set of data that contributed to the alert such that the alert-contributing set of data can be used to respond to the prospective query upon arrival thereof.

2. The method of claim 1, further comprising the step of storing the alert-contributing set of data in a query results storage element.

3. The method of claim 1, wherein an alert comprises a computation result of interest.

4. The method of claim 1, wherein determination of the alert-contributing set of data further comprises:

representing the data stream processing system as a processing graph wherein nodes of the processing graph correspond to processing elements in the data stream processing system and links in the processing graph correspond to communication paths between the processing elements; and

creating an overlay graph wherein nodes in the overlay graph correspond to nodes in the processing graph, and links in the overlay graph correspond to links in the processing graph.

5. The method of claim 4, wherein:

each link in the overlay graph is a reverse of the corresponding link in the processing graph, and the overlay nodes operate concurrently with the nodes in the processing graph; and

starting with a node that generated the alert, each node uses dependency information to forward to its linked nodes data that was forwarded to its corresponding node in the processing graph from the processing graph node corresponding to the linked node and that contributed to the alert.

6. The method of claim 1, wherein the alert-contributing set of data is stored for a designated duration.

7. The method of claim 1, wherein the alert-contributing set of data is marked for storage with a retention value that is based on a priority associated with the alert.

8. The method of claim 1, wherein the step of triggering the scheduler further comprises associating the alert with one or more classes of alerts.

9. The method of claim 8, wherein the scheduler generates a schedule based on a history of prior queries issued for a corresponding class.

10. The method of claim 8, wherein the scheduler generates a schedule based on a rule describing likely time instants at which a query for the corresponding class may be issued.

11. Apparatus for processing data associated with a data stream received by a data stream processing system, wherein the system comprises a plurality of processing elements, the apparatus comprising:

a memory; and

a processor coupled to the memory and configured to;

maintain a portion of data associated with the data stream, wherein the maintained data comprises inputs to each processing element that contributed to an output of each processing element;

in response to an alert generated by one of the processing elements, trigger a scheduler to determine when a pre-calculation of a prospective query related to the alert should be executed; and

in response to the scheduler, use at least a portion of the maintained data to determine a set of data that contributed to the alert such that the alert-contributing set of data can be used to respond to the prospective query upon arrival thereof.

12. The apparatus of claim 11, wherein the processor is further configured to store the alert-contributing set of data in a query results storage element.

13. The apparatus of claim 11, wherein an alert comprises a computation result of interest.

14. The apparatus of claim 11, wherein determination of the alert-contributing set of data further comprises:

representing the data stream processing system as a processing graph wherein nodes of the processing graph correspond to processing elements in the data stream processing system and links in the processing graph correspond to communication paths between the processing elements; and

creating an overlay graph wherein nodes in the overlay graph correspond to nodes in the processing graph, and links in the overlay graph correspond to links in the processing graph.

15. The apparatus of claim 14, wherein:

each link in the overlay graph is a reverse of the corresponding link in the processing graph, and the overlay nodes operate concurrently with the nodes in the processing graph; and

starting with a node that generated the alert, each node uses dependency information to forward to its linked nodes data that was forwarded to its corresponding node in the processing graph from the processing graph node corresponding to the linked node and that contributed to the alert.

16. The apparatus of claim 11, wherein the alert-contributing set of data is stored for a designated duration.

17. The apparatus of claim 11, wherein the alert-contributing set of data is marked for storage with a retention value that is based on a priority associated with the alert.

18. The apparatus of claim 11, wherein triggering the scheduler further comprises associating the alert with one or more classes of alerts.

19. The apparatus of claim 18, wherein the scheduler generates a schedule based on at least one of:

a history of prior queries issued for a corresponding class; and

a rule describing likely time instants at which a query for the corresponding class may be issued.

20. An article of manufacture for processing data associated with a data stream received by a data stream processing system, wherein the system comprises a plurality of processing elements, the article comprising a computer readable storage medium having one or more programs embodied therewith wherein the one or more programs, when executed by a computer, perform steps of:

maintaining a portion of data associated with the data stream, wherein the maintained data comprises inputs to each processing element that contributed to an output of each processing element;

in response to an alert generated by one of the processing elements, triggering a scheduler to determine when a pre-calculation of a prospective query related to the alert should be executed; and

in response to the scheduler, using at least a portion of the maintained data to determine a set of data that contributed to the alert such that the alert-contributing set of data can be used to respond to the prospective query upon arrival thereof.