Data streams are de?ned as large sequences of data, gathered from sources such as sensor networks and customer click streams, that are possibly in?nite and temporarily ordered [7, 22]. Instances in data streams arrive fast, either in batches of data, or instance-by-instance; each instance needs to be processed in a timely manner. Due to these characteristics, such as large amount of data and time constraints, tra-ditional static machine learning algorithms are unsuitable for direct use [7]. That is, techniques learning from data streams need to maintain their performance throughout the stream while limiting memory and processing time.