Query-aware sampling of data streams

• US 20090187584A1
• Filed: 03/30/2009
• Published: 07/23/2009
• Est. Priority Date: 03/21/2006
• Status: Active Grant

• Current Assignee: AT&T Corporation (AT&T, Inc.)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Shkapenyuk, Vladislav, Spatscheck, Oliver, Muthukrishnan, Shanmugavelayutham, Johnson, Theodore
• Granted Patent: US 8,108,394 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: H04L 43/022 by sampling

Abstract

A system, method and computer-readable medium provide for assigning sampling methods to each input stream for arbitrary query sets in a data stream management system. The method embodiment comprises splitting all query nodes in a query directed acyclic graph (DAG) having multiple parent nodes into sets of independent nodes having a single parent, computing a grouping set for every node in each set of independent nodes, reconciling each parent node with each child node in each set of independent node, reconciling between multiple child nodes that share a parent node and generating a final grouping set for at least one node describing how to sample an input stream for that node.

Claims

1. A method of assigning sampling methods to each input stream for arbitrary query sets in a data stream management system, the method comprising:

splitting all query nodes in a query directed acyclic graph (DAG) having multiple parent nodes into sets of independent nodes having a single parent node; and

generating via a processor a final grouping set based on a reconciliation between the multiple child nodes that share a parent node for at least one node describing how to sample an input stream for the at least one node.

2. The method of claim 1, further comprising computing a grouping set for every node in each set of independent nodes.

3. The method of claim 2, further comprising reconciling each parent node with each child node in each set of independent nodes.

4. The method of claim 3, further comprising reconciling between multiple child nodes that share a parent node that share the parent node.

5. The method of claim 1, further comprising labeling sampling unsafe nodes.

6. The method of claim 1, wherein the final grouping set comprises a labeling of each leaf node with a compatible sampling method.

7. The method of claim 2, wherein computing a grouping set for every node is performed using a single node grouping set analysis.

8. A system for assigning sampling methods to each input stream for arbitrary query sets in a data stream management system, the system comprising:

a processor;

a module configured to control the processor to split all query nodes in a query directed acyclic graph (DAG) having multiple parent nodes into sets of independent nodes having a single parent node; and

a module configured to control the processor to generate a final grouping set based on a reconciliation between the multiple child nodes that share a parent node for at least one node describing how to sample an input stream for the at least one node.

9. The system of claim 8, wherein the final grouping set for the at least one node further describes what records should be dropped by the data stream management system.

10. The system of claim 9, wherein the data stream management system implements the sampling associated with the final grouping set for at least one node based on a threshold associated with flow of data stream records.

11. A tangible computer-readable storing instructions for controlling a computing device to assign sampling methods to each input stream for arbitrary query sets in a data stream management system, the instructions comprising:

splitting all query nodes in a query directed acyclic graph (DAG) having multiple parent nodes into sets of independent nodes having a single parent node; and

generating via a processor a final grouping set based on a reconciliation between the multiple child nodes that share a parent node for at least one node describing how to sample an input stream for the at least one node.

12. The tangible computer-readable medium of claim 11, wherein the instructions further comprise computing a grouping set for every node in each set of independent nodes.

13. The tangible computer-readable medium of claim 12, further comprising reconciling each parent node with each child node in each set of independent nodes.

14. The tangible computer-readable medium of claim 13, further comprising reconciling between multiple child nodes that share the parent node that share the parent node.

15. The computer readable storage medium of claim 13, wherein the final grouping set comprises a labeling of each leaf node with a compatible sampling method.

16. The computer readable storage medium of claim 13, wherein computing a grouping set for every node is performed using a single node grouping set analysis.

17. The computer readable storage medium of claim 13, wherein the final grouping set for the at least one node further describes what records should be dropped by the data stream management system.

18. The computer readable storage medium of claim 17, wherein the data stream management system implements the sampling associated with the final grouping set for at least one node based on a threshold associated with flow of data stream records.