Random sampling from distributed streams

• US 8,392,434 B1
• Filed: 09/16/2011
• Issued: 03/05/2013
• Est. Priority Date: 09/16/2011
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation, Iowa State University Research Foundation Incorporated (Iowa State University)
• Original Assignee: International Business Machines Corporation, Iowa State University
• Inventors: Woodruff, David P., Tirthapura, Srikanta N.
• Primary Examiner(s): LEWIS, CHERYL RENEA
• Application Number:
  US13/234,420
• Publication Number:
  US 20130073561A1
• Time in Patent Office: 536 Days
• Field of Search: 707/748, 707/999.101
• US Class Current: 707/748
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries
• CPC Class Codes: G06F 16/2458 Special types of queries, e.g. statistical queries, fuzzy queries or distributed queries
• CPC Class Codes: G06F 16/2462 Approximate or statistical queries

Abstract

Described herein are methods, systems, apparatuses and products for random sampling from distributed streams. An aspect provides a method for distributed sampling on a network with a plurality of sites and a coordinator, including: receiving at the coordinator a data element from a site of the plurality of sites, said data element having a weight randomly associated therewith deemed reportable by comparison at the site to a locally stored global value; comparing the weight of the data element received with a global value stored at the coordinator; and performing one of: updating the global value stored at the coordinator to the weight of the data element received; and communicating the global value stored at the coordinator back to the site of the plurality of sites. Other embodiments are disclosed.

Claims

1. A method for distributed sampling on a network with a plurality of sites and a coordinator, comprising:

receiving at the coordinator a data element from a site of the plurality of sites, said data element having a weight randomly associated therewith deemed reportable by comparison at the site to a locally stored global value;

comparing the weight of the data element received with a global value stored at the coordinator; and

performing one of;

updating the global value stored at the coordinator to the weight of the data element received; and

communicating the global value stored at the coordinator back to the site of the plurality of sites.

2. The method of claim 1, wherein the weight randomly associated with the data element at the site is deemed reportable by the site if the weight randomly associated with the data element is less than the locally stored global value at the site.

3. The method of claim 2, wherein the communicating the global value stored at the coordinator back to the site of the plurality of sites is performed responsive to a determination that the weight randomly associated with the data element received is greater than the global value stored at the coordinator.

4. The method of claim 3, wherein the updating the global value stored at the coordinator to the weight of the data element received is performed responsive to a determination that the weight randomly associated with the data element received is less than the global value stored at the coordinator.

5. The method of claim 1, wherein the weight randomly associated with the data element at the site is deemed reportable by the site if the weight randomly associated with the data element is greater than the locally stored global value.

6. The method of claim 5, wherein the communicating the global value stored at the coordinator back to the site of the plurality of sites is performed responsive to a determination that the weight randomly associated with the data element received less than the global value stored at the coordinator.

7. The method of claim 6, wherein the updating the global value stored at the coordinator to the weight of the data element received is performed responsive to a determination that the weight randomly associated with the data element received is greater than the global value stored at the coordinator.

8. The method of claim 1, further comprising:

at each site;

receiving a plurality of data elements from a data stream;

associating a random weight to each of the plurality of elements; and

responsive to a data element being associated with a random weight below the locally stored global value at a receiving site, sending the data element to the coordinator.

9. The method of claim 1, further comprising storing, at the coordinator, at least one received data element from the plurality of sites.

10. The method of claim 1, further comprising estimating a number of distinct elements using the global value stored at the coordinator.

11. The method of claim 1, further comprising:

receiving a query at the coordinator; and

answering said query using a random sample based on at least one data element stored at the coordinator.

12. The method of claim 1, wherein said plurality of sites are network routers, and further wherein said network routers are connected to said coordinator via at least one network connection.

13. A computer program product for distributed sampling on a network with a plurality of sites and a coordinator, comprising:

a computer readable storage medium having computer readable program code embodied therewith, the computer readable program code comprising;

computer readable program code configured to receive, at the coordinator, a data element from a site of the plurality of sites, said data element having a weight randomly associated therewith deemed reportable by comparison at the site to a locally stored global value;

computer readable program code configured to compare the weight of the data element received with a global value stored at the coordinator; and

computer readable program code configured to perform one of;

updating the global value stored at the coordinator to the weight of the data element received; and

communicating the global value stored at the coordinator back to the site of the plurality of sites.

14. The computer program product of claim 13, wherein the computer readable program code configured to communicate the global value stored at the coordinator back to the site of the plurality of sites is further configured to communicate the global value responsive to a determination that the weight randomly associated with the data element received is greater than the global value stored at the coordinator.

15. The computer program product of claim 14, wherein computer readable program code configured to update the global value stored at the coordinator to the weight of the data element received is further configured to update the global value stored at the coordinator responsive to a determination that the weight randomly associated with the data element received is less than the global value stored at the coordinator.

16. The computer program product of claim 13, wherein the computer readable program code configured to communicate the global value stored at the coordinator back to the site of the plurality of sites is further configured to communicate the global value responsive to a determination that the weight randomly associated with the data element received less than the global value stored at the coordinator.

17. The computer program product of claim 16, wherein the computer readable program code configured to update the global value stored at the coordinator to the weight of the data element received is further configured to update the global value at the coordinator responsive to a determination that the weight randomly associated with the data element received is greater than the global value stored at the coordinator.

18. The computer program product of claim 13, further comprising computer readable program code configured to:

store, at the coordinator, at least one received data element from the plurality of sites;

receive a query at the coordinator; and

answer said query using a random sample based on at least one data element stored at the coordinator.

19. The computer program product of claim 13, wherein said plurality of sites are network routers, and further wherein said network routers are connected to said coordinator via at least one network connection.

20. A system comprising:

at least one processor; and

a memory device operatively connected to the at least one processor;

wherein, responsive to execution of program instructions accessible to the at least one processor, the at least one processor is configured to;

receive at the coordinator a data element from a site of the plurality of sites, said data element having a weight randomly associated therewith deemed reportable by comparison at the site to a locally stored global value;

compare the weight of the data element received with a global value stored at the coordinator; and

perform one of;

updating the global value stored at the coordinator to the weight of the data element received; and

communicating the global value stored at the coordinator back to the site of the plurality of sites.