Methods and Apparatus for Adaptive Source Filtering and Load Shedding for Data Stream Processing

• US 20090100014A1
• Filed: 10/10/2007
• Published: 04/16/2009
• Est. Priority Date: 10/10/2007
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: WU, KUN-LUNG, GEDIK, BUGRA, YU, PHILIP SHI-LUNG
• Granted Patent: US 9,158,837 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/3331 Query processing
• CPC Class Codes: G06F 16/3332 Query translation

Abstract

Techniques are disclosed for adaptive source filtering and load shedding in such data stream processing systems. For example, in one aspect of the invention, a method for use in filtering data in a distributed data stream processing system, wherein a server receives and processes one or more data streams from one or more data sources, comprises the steps of the server periodically re-configuring one or more filters and sending the one or more periodically re-configured filters to the one or more data sources, and the one or more data sources performing data filtering based on the one or more periodically re-configured filters received from the server.

Claims

1. A method for use in filtering data in a distributed data stream processing system, wherein a server receives and processes one or more data streams from one or more data sources, the method comprising the steps of:

the server periodically re-configuring one or more filters and sending the one or more periodically re-configured filters to the one or more data sources; and

the one or more data sources performing data filtering based on the one or more periodically re-configured filters received from the server.

2. The method of claim 1, wherein the step of the server periodically re-configuring the one or more filters further comprises the steps of:

defining one or more non-overlapping regions of a data space associated with at least one of the one or more filters; and

determining a drop threshold for each of the one or more non-overlapping regions within the filter.

3. The method of claim 2, wherein the step of the server defining one or more non-overlapping regions of the data space for the filter further comprises the step of partitioning the data space of the filter into a given number of regions.

4. The method of claim 3, wherein the given number of regions are equally sized.

5. The method of claim 3, wherein, for the given number of regions, a data frequency is the same.

6. The method of claim 3, wherein, for the given number of regions, a query density is the same.

7. The method of claim 3, wherein, for the given number of regions, a partition benefit is maximized.

8. The method of claim 2, wherein the step of the server determining a drop threshold for each region within the filter further comprises the steps of:

consolidating queries intersecting each filter region into one QoS value region; and

formulating the drop threshold determination step into an optimization problem.

9. The method of claim 8, wherein the step of consolidating queries further comprises the steps of:

decomposing the QoS value of each query into one or more additive components, each component per intersected filter region; and

for each filter region, consolidating the QoS components of different queries that intersect the region into a single QoS value.

10. The method of claim 8, wherein the step of formulating the optimization problem further comprises the steps of:

setting an objective function to an aggregate of the QoS values of the region; and

setting constraints such that the total fraction of a load shed using the drop thresholds equals a pre-calculated throttler value.

11. The method of claim 10, wherein the throttler value is pre-calculated by the steps of:

monitoring a system utilization since a last adaptation step;

monitoring a fraction of dropped data items; and

using the monitoring steps to compute a fraction of the load that can be handled, wherein the computed fraction is the throttler value.

12. An article of manufacture for use in filtering data in a distributed data stream processing system, comprising computer readable storage medium containing one or more programs which, when executed by a computer, performs the steps of claim 1.

13. Apparatus for use in filtering data in a distributed data stream processing system, wherein the apparatus receives and processes one or more data streams from one or more data sources, the apparatus comprising:

a memory; and

a processor coupled to the memory and operative to periodically re-configure one or more filters and send the one or more periodically re-configured filters to the one or more data sources such that the one or more data sources are able to perform data filtering based on the one or more periodically re-configured filters.

14. The apparatus of claim 13, wherein the operation of periodically re-configuring the one or more filters further comprises:

defining one or more non-overlapping regions of a data space associated with at least one of the one or more filters; and

determining a drop threshold for each of the one or more non-overlapping regions within the filter.

15. The apparatus of claim 14, wherein the operation of the server defining one or more non-overlapping regions of the data space for the filter further comprises partitioning the data space of the filter into a given number of regions.

16. The apparatus of claim 14, wherein the operation of determining a drop threshold for each region within the filter further comprises:

consolidating queries intersecting each filter region into one QoS value region; and

formulating the drop threshold determination step into an optimization problem.

17. A query server, wherein the query server receives and processes one or more data streams from one or more data sources, the query server comprising:

a memory; and

a processor coupled to the memory and operative to periodically re-configure one or more filters and send the one or more periodically re-configured filters to the one or more data sources such that the one or more data sources are able to perform data filtering based on the one or more periodically re-configured filters.

18. The query server of claim 17, wherein the operation of periodically re-configuring the one or more filters further comprises:

defining one or more non-overlapping regions of a data space associated with at least one of the one or more filters; and

determining a drop threshold for each of the one or more non-overlapping regions within the filter.

19. The query server of claim 18, wherein the operation of the server defining one or more non-overlapping regions of the data space for the filter further comprises partitioning the data space of the filter into a given number of regions.

20. The query server of claim 18, wherein the operation of determining a drop threshold for each region within the filter further comprises:

consolidating queries intersecting each filter region into one QoS value region; and

formulating the drop threshold determination step into an optimization problem.