System and method for load shedding in data mining and knowledge discovery from stream data
First Claim
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;
making one or more load shedding decisions based on historic feature values;
thereafter shedding a plurality of data stream elements according to the one or more load shedding decisions;
providing one or more predicted feature values for one or more of said plurality of data stream elements shed; and
performing a data mining task using both the one or more predicted feature values of the one or more plurality of data stream elements shed and real values for one or more data stream elements not shed.
1 Assignment
0 Petitions
Accused Products
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.
13 Citations
19 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; making one or more load shedding decisions based on historic feature values; thereafter shedding a plurality of data stream elements according to the one or more load shedding decisions; providing one or more predicted feature values for one or more of said plurality of data stream elements shed; and performing a data mining task using both the one or more predicted feature values of the one or more plurality of data stream elements shed and real values for one or more data stream elements not shed. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
-
-
10. 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 making one or more load shedding decisions based on historic feature values; an arrangement for thereafter shedding a plurality of data stream elements according to the one or more load shedding decisions; and a processor to; provide one or more predicted feature values for one or more of said plurality of data scream elements shed; and perform a data mining task using both the one or more predicted feature values of the one or more plurality of data stream elements shed and real values for one or more data stream elements not shed. - View Dependent Claims (11, 12, 13, 14, 15, 16, 17, 18)
-
-
19. A program storage device readable by machine, tangibly embodying a program of instructions executable by the machine to perform method steps for:
-
accepting streams of data to be mined, the streams of data containing data stream elements; making one or more load shedding decisions based on historic feature values; thereafter shedding a plurality of data stream elements according to the one or more load shedding decisions; providing one or more predicted feature values for one or more of said plurality of data stream elements shed; and performing a data mining task using both the one or more predicted feature values of the one or more plurality of data stream elements shed and real values for one or more data stream elements not shed.
-
Specification