SYSTEM AND METHOD FOR ANALYZING STREAMS AND COUNTING STREAM ITEMS ON MULTI-CORE PROCESSORS

• US 20090031175A1
• Filed: 07/26/2007
• Published: 01/29/2009
• Est. Priority Date: 07/26/2007
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: AGGARWAL, CHARU CHANDRA, THOMAS, DINA, YU, PHILIP SHILUNG, BORDAWEKAR, RAJESH
• Granted Patent: US 8,321,579 B2
• Time in Patent Office: Days
• US Class Current: 714/47
• CPC Class Codes: G06F 17/18 for evaluating statistical data , e.g. average values, frequency distributions, probability functions, regression analysis forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04

Abstract

Systems and methods for parallel stream item counting are disclosed. A data stream is partitioned into portions and the portions are assigned to a plurality of processing cores. A sequential kernel is executed at each processing core to compute a local count for items in an assigned portion of the data stream for that processing core. The counts are aggregated for all the processing cores to determine a final count for the items in the data stream. A frequency-aware counting method (FCM) for data streams includes dynamically capturing relative frequency phases of items from a data stream and placing the items in a sketch structure using a plurality of hash functions where a number of hash functions is based on the frequency phase of the item. A zero-frequency table is provided to reduce errors due to absent items.

Claims

1. A method for parallel stream item counting, comprising:

partitioning a data stream into portions;

assigning the portions to a plurality of processing cores; and

executing a sequential kernel on a computer useable medium including a computer readable program, wherein the computer readable program when executed on the processing core causes the processing core to compute a local count for items in an assigned portion of the data stream for that processing core.

2. The method as recited in claim 1, wherein partitioning a data stream into portions includes partitioning the data stream into portions by a hash-based partitioning.

3. The method as recited in claim 2, wherein the hash-based partitioning includes providing values for items in the data streams and placing the items in buckets based on the values.

4. The method as recited in claim 1, wherein partitioning a data stream into portions includes partitioning the data stream into portions by a block-based partitioning.

5. The method as recited in claim 4, wherein the block-based partitioning includes dividing the data stream into equal-sized blocks of data.

6. The method as recited in claim 1, further comprising:

querying participating processing cores for a count;

responsive to the query, determining for each participating processing core, a local item count; and

summing up the local item counts to provide a final result for the query.

7. The method as recited in claim 1, wherein executing a sequential kernel includes a frequency-aware counting method (FCM).

8. The method as recited in claim 1, wherein executing the FCM sequential kernel includes:

providing a sketch structure to dynamically capture relative frequency phases of items from the data stream;

utilizing a plurality of hash functions based on the frequency phase; and

providing a zero-frequency table to reduce errors due to absent items.

9. A computer readable medium comprising a computer readable program for parallel stream item counting wherein the computer readable program when executed on a computer causes the computer to perform the steps as recited in claim 1.

10. A frequency-aware counting method (FCM) for data streams, comprising:

dynamically capturing relative frequency phases of items from a data stream;

placing the items in a sketch structure using a plurality of hash functions where a number of hash functions is based on the frequency phase of the item; and

providing a zero-frequency table to reduce errors due to absent items.

11. The method as recited in claim 10, wherein dynamically capturing relative frequency phases including employing a Misra-Gries counter to track items.

12. The method as recited in claim 11, wherein employing a Misra-Gries counter to track items includes:

tracking items whose phase frequency satisfies a condition; and

returning the items that satisfy the condition.

13. The method as recited in claim 10, wherein placing the items in a sketch structure includes determining an offset, gap and number of hash functions for each item and incrementing buckets in the sketch structure based upon the hash functions.

14. The method as recited in claim 10, wherein providing a zero-frequency table to reduce errors due to absent items including using all hash functions to increment buckets in the zero-frequency table.

15. The method as recited in claim 10, further comprising:

in response to a query, determining an offset and a gap in the sketch structure from each item; and

computing a count estimate from the sketch structure by minimizing values over buckets with averaged numbers of hash functions.

16. The method as recited in claim 15, further comprising:

computing a count estimate from the zero-frequency table by minimizing values over all buckets; and

computing a final count as the minimum of count estimates from the sketch structure and the zero-frequency table.

17. A computer readable medium comprising a computer readable program for a frequency-aware counting method (FCM) for data streams wherein the computer readable program when executed on a computer causes the computer to perform the steps as recited in claim 10.

18. A multiprocessor, comprising:

a plurality of processing cores, which include a coordinating processor core, and at least one other processing core managed by the coordinating processing core;

the plurality of processing cores being configured to receive and partition a data stream into portions to permit parallel counting for items in the data stream;

a sequencing kernel executed by each of the core processors to implement a frequency-aware counting method, the frequency aware counting method including;

a sketch structure configured to store item counts using a plurality of hash functions where a number of hash functions is based on the frequency phase of the item; and

a zero-frequency table configured to reduce errors due to absent items using all of the hash functions.

19. The multiprocessor as recited in claim 18, wherein the sketch structure and the zero-frequency table include buckets associated with the hash functions that are incremented to provide item counts.

20. The microprocessor as recited in claim 19, further comprising:

a first count estimate obtained from the sketch structure by minimizing values over averaged buckets;

a second count estimate obtained from the zero-frequency table by minimizing values over all buckets; and

a final count selected as the minimum of the first and second count estimates.