Query-aware sampling of data streams

• US 7,536,396 B2
• Filed: 10/30/2006
• Issued: 05/19/2009
• Est. Priority Date: 03/21/2006
• Status: Expired due to Fees

• Current Assignee: AT&T Corporation (AT&T, Inc.)
• Original Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Inventors: Spatscheck, Oliver, Shkapenyuk, Vladislav, Muthukrishnan, Shanmugavelayutham, Johnson, Theodore
• Primary Examiner(s): Wong, Don
• Assistant Examiner(s): Nguyen, Merilyn P
• Application Number:
  US11/554,327
• Publication Number:
  US 20070226239A1
• Time in Patent Office: 932 Days
• Field of Search: 707 1- 3, 707100-102, 707/103.R, 707/104.1
• 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, tile 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 via a processor 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 based on the reconciliation between the multiple child nodes that share the 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 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, tile 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;

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

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

a module configured to control the processor to reconcile between multiple child nodes that share

a parent node; and

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

8. The system of claim 7, further comprising a module configured to control the processor 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 the module configured to control the processor to compute a grouping set for every node further computes the grouping set 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 storage medium 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;

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 based on the reconciliation between the multiple child nodes that share the parent node for at least one node describing how to sample an input stream for the at least one node.

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

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.