Method and apparatus for data stream sampling

• US 20070226188A1
• Filed: 03/27/2006
• Published: 09/27/2007
• Est. Priority Date: 03/27/2006
• Status: Abandoned Application

• Current Assignee: AT&T Corporation (AT&T, Inc.)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Muthukrishnan, Shanmugavelayutham, Johnson, Theodore, Rozenbaum, Irina
• Application Number:
  US11/389,851
• Publication Number:
  US 20070226188A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries
• CPC Class Codes: G06F 16/2474 Sequence data queries, e.g. querying versioned data
• CPC Class Codes: H04L 43/022 by sampling

Abstract

In one embodiment, the present invention is a method and apparatus for data stream sampling. In one embodiment, a tuple of a data stream is received from a sampling window of the data stream. The tuple is associated with a group, selected from a set of one or more groups, which reflects a subset of information relating to a sample of the data stream. In addition, the tuple is associated with a supergroup, selected from a set of one or more supergroups, which reflects global information relating to the sample. It is then determined whether receipt of the tuple triggers a cleaning phase in which one or more tuples are shed from the sample. The operator can be implemented to execute a variety of different sampling algorithms, including well-known and experimental algorithms.

Claims

1. A method for sampling a data stream comprising a plurality of tuples, the operator comprising:

receiving one of said plurality of tuples, said one of said plurality of tuples belonging to a first sampling window;

associating said one of said plurality of tuples with a group, selected from a set of one or more groups, that reflects a subset of information relating to a sample of said data stream;

associating said one of said plurality of tuples with a supergroup, selected from a set of one or more supergroups, that reflects global information relating to said sample; and

applying one or more cleaning criteria to each of said one or more groups, if reception of said one of said plurality of tuples triggers a cleaning phase.

2. The method of claim 1, wherein said receiving comprises:

processing said one of said plurality of tuples, if said one of said plurality of tuples satisfies one or more predefined sampling criteria; and

discarding said one of said plurality of tuples, if said one of said plurality of tuples does not satisfy said one or more predefined sampling criteria.

3. The method of claim 1, wherein said associating said one of said plurality of tuples with a group comprises:

identifying a group defined by a key that is associated with said one of said plurality of tuples.

4. The method of claim 1, wherein said associating said one of said plurality of tuples with a group comprises:

creating a new group defined by a key that is associated with said one of said plurality of tuples.

5. The method of claim 1, wherein said associating said one of said plurality of tuples with a supergroup comprises:

identifying a supergroup defined by a key that is associated with said one of said plurality of tuples.

6. The method of claim 1, wherein said associating said one of said plurality of tuples with a supergroup comprises:

creating a new supergroup defined by a key that is associated with said one of said plurality of tuples.

7. The method of claim 1, further comprising:

applying one or more sampling criteria to each of said one or more groups;

sampling each of said one or more groups that satisfies said sampling criteria; and

discarding each of said one or more groups that does not satisfy said sampling criteria.

8. The method of claim 1, wherein said global information is maintained by one or more stateful functions, said one or more stateful functions requiring access a global state function throughout execution of said operator.

9. The method of claim 1, further comprising:

applying one or more cleaning criteria to each of said one or more groups, if reception of said one of said plurality of tuples triggers a cleaning phase.

10. A computer readable medium containing an executable program for sampling a data stream comprising a plurality of tuples, where the program performs the steps of:

receiving one of said plurality of tuples, said one of said plurality of tuples belonging to a first sampling window;

associating said one of said plurality of tuples with a group, selected from a set of one or more groups, that reflects a subset of information relating to a sample of said data stream;

associating said one of said plurality of tuples with a supergroup, selected from a set of one or more supergroups, that reflects global information relating to said sample; and

applying one or more cleaning criteria to each of said one or more groups, if reception of said one of said plurality of tuples triggers a cleaning phase.

11. The computer readable medium of claim 10, wherein said receiving comprises:

processing said one of said plurality of tuples, if said one of said plurality of tuples satisfies one or more predefined sampling criteria; and

discarding said one of said plurality of tuples, if said one of said plurality of tuples does not satisfy said one or more predefined sampling criteria.

12. The computer readable medium of claim 10, wherein said associating said one of said plurality of tuples with a group comprises:

identifying a group defined by a key that is associated with said one of said plurality of tuples.

13. The computer readable medium of claim 10, wherein said associating said one of said plurality of tuples with a group comprises:

creating a new group defined by a key that is associated with said one of said plurality of tuples.

14. The computer readable medium of claim 10, wherein said associating said one of said plurality of tuples with a supergroup comprises:

identifying a supergroup defined by a key that is associated with said one of said plurality of tuples.

15. The computer readable medium of claim 10, wherein said associating said one of said plurality of tuples with a supergroup comprises:

creating a new supergroup defined by a key that is associated with said one of said plurality of tuples.

16. The computer readable medium of claim 10, further comprising:

applying one or more cleaning criteria to each of said one or more groups, if reception of said one of said plurality of tuples triggers a cleaning phase.

17. The computer readable medium of claim 10, further comprising:

applying one or more sampling criteria to each of said one or more groups;

sampling each of said one or more groups that satisfies said sampling criteria; and

discarding each of said one or more groups that does not satisfy said sampling criteria.

18. The computer readable medium of claim 10, wherein said global information is maintained by one or more stateful functions, said one or more stateful functions requiring access a global state function throughout execution of said operator.

19. An apparatus for sampling a data stream comprising a plurality of tuples, the apparatus comprising:

means for receiving one of said plurality of tuples, said one of said plurality of tuples belonging to a first sampling window;

means for associating said one of said plurality of tuples with a group, selected from a set of one or more groups, that reflects a subset of information relating to a sample of said data stream; and

means for associating said one of said plurality of tuples with a supergroup, selected from a set of one or more supergroups, that reflects global information relating to said sample; and

means for applying one or more cleaning criteria to each of said one or more groups, if reception of said one of said plurality of tuples triggers a cleaning phase.

20. The apparatus of claim 19, wherein said means for receiving comprises:

means for processing said one of said plurality of tuples, if said one of said plurality of tuples satisfies one or more predefined sampling criteria; and

means for discarding said one of said plurality of tuples, if said one of said plurality of tuples does not satisfy said one or more predefined sampling criteria.