QUERY-AWARE SAMPLING OF DATA STREAMS

• US 20070226239A1
• Filed: 10/30/2006
• Published: 09/27/2007
• 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 7,536,396 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;

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 nodes;

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.

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

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

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

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

6. The method of claim 5, 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.

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

a module configured 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;

a module configured to compute a grouping set for every node in each set of independent nodes;

a module configured to reconcile each parent node with each child node in each set of independent nodes;

a module configured to reconcile between multiple child nodes that share a parent node; and

a module configured to generate a final grouping set for at least one node describing how to sample an input stream for that node.

8. The system of claim 7, further comprising a module configured to label sampling unsafe nodes.

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

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

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

12. The system of claim 11, 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.

13. A computer readable medium storing instructions for controlling a computing device to assigning 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;

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 nodes;

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.

14. The computer readable medium of claim 13, the instructions further comprising labeling sampling unsafe nodes.

15. The computer readable 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 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 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 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.