SYSTEM AND METHOD FOR LOAD SHEDDING IN DATA MINING AND KNOWLEDGE DISCOVERY FROM STREAM DATA

• US 20090187914A1
• Filed: 02/17/2009
• Published: 07/23/2009
• Est. Priority Date: 02/16/2005
• Status: Active Grant

• Current Assignee: AirBNB Incorporated
• Original Assignee: International Business Machines Corporation
• Inventors: Yu, Philip S., Chi, Yun, Wang, Haixun
• Granted Patent: US 8,060,461 B2
• Time in Patent Office: Days
• US Class Current: 718/103
• CPC Class Codes: G06F 18/295 Markov models or related models, e.g. semi-Markov models; Markov random fields; Networks embedding Markov models
• CPC Class Codes: H04L 43/028 by filtering

Abstract

Load shedding schemes for mining data streams. A scoring function is used to rank the importance of stream elements, and those elements with high importance are investigated. In the context of not knowing the exact feature values of a data stream, the use of a Markov model is proposed herein for predicting the feature distribution of a data stream. Based on the predicted feature distribution, one can make classification decisions to maximize the expected benefits. In addition, there is proposed herein the employment of a quality of decision (QoD) metric to measure the level of uncertainty in decisions and to guide load shedding. A load shedding scheme such as presented herein assigns available resources to multiple data streams to maximize the quality of classification decisions. Furthermore, such a load shedding scheme is able to learn and adapt to changing data characteristics in the data streams.

Claims

1. A method of providing load shedding in mining data streams, said method comprising the steps of:

accepting streams of data to be mined, the streams of data containing data stream elements;

ranking the importance of data stream elements;

investigating data stream elements of higher importance; and

thereafter shedding a plurality of data stream elements;

wherein the plurality of data stream elements shed have a higher quality of decision value than the data stream elements of higher importance and the quality of decision value is based on the predicted distribution of feature values in a next time unit.

2. The method according to claim 1, further comprising the step of predicting the feature distribution of at least one data stream.

3. The method according to claim 2, wherein said predicting step comprises employing a Markov model.

4. The method according to claim 2, further comprising the step of rendering classification decisions based on the predicted feature distribution of at least one data stream.

5. The method according to claim 4, wherein said step of rendering classification decisions comprises rendering classification decisions with a view to maximizing expected benefits.

6. The method according to claim 1, wherein said ranking step comprises employing a quality of decision metric to assist in classification decisions.

7. The method according to claim 6, wherein said step of employing a quality of decision metric comprises measuring uncertainty in classification decisions.

8. The method according to claim 7, wherein said step of employing a quality of decision metric comprises applying the quality of decision metric to multiple data streams.

19. The method according to claim 1, wherein the quality of decision value is Q₂=1−

(E_x[R(c_k|x)]−

E_x[R(c*|x)]).

9. An apparatus for providing load shedding in mining data streams, said apparatus comprising:

an arrangement for accepting streams of data to be mined, the streams of data containing data stream elements;

an arrangement for ranking the importance of data stream elements;

an arrangement for investigating data stream elements of higher importance; and

an arrangement for shedding a plurality of data stream elements;

wherein the plurality of data stream elements shed have a higher quality of decision value than the data stream elements of higher importance and the quality of decision value is based on the predicted distribution of feature values in a next time unit;

a processor to rank the data stream elements.

10. The apparatus according to claim 9, further comprising an arrangement for predicting the feature distribution of at least one data stream.

11. The apparatus according to claim 10, wherein said predicting arrangement is adapted to employ a Markov model.

12. The apparatus according to claim 10, further comprising an arrangement for rendering classification decisions based on the predicted feature distribution of at least one data stream.

13. The apparatus according to claim 12, wherein said arrangement for rendering classification decisions is adapted to render classification decisions with a view to maximizing expected benefits.

14. The apparatus according to claim 9, wherein said ranking arrangement is adapted to employ a quality of decision metric to assist in classification decisions.

15. The apparatus according to claim 14, wherein said arrangement for employing a quality of decision metric is adapted to measure uncertainty in classification decisions.

16. The apparatus according to claim 15, wherein said arrangement for employing a quality of decision metric is adapted to apply the quality of decision metric to multiple data streams.

18. The apparatus according to claim 9, wherein the quality of decision value is

$Q_1=E_x$

log 

( f k 

( x ) f k _ 

( x ) ) .

17. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for:

accepting data streams to be mined, the data streams containing data stream elements;

ranking the importance of data stream elements;

investigating data stream elements of higher importance; and

thereafter shedding a plurality of data stream elements;

wherein the plurality of data stream elements shed have a higher quality of decision value than the data stream elements of higher importance and the quality of decision value is based on the predicted distribution of feature values in a next time unit.