Narrow Results

Every second, a huge volume of multi-dimensional data is generated in fields such as Social Networking, Industrial Internet of Things, Stock market and E-commerce applications. Knowledge and pattern extraction are a challenging task in the evolving nature of data stream. Major issues are (i) ‘concept drift’ occurs as a result of pattern changes in the data distribution and (ii) ‘concept evolution’ occurs when a new class evolves in the data stream. These issues degrade the performance of learning models. In this paper, we focus on detection of concept evolution and enhance the performance of classifiers. For this, we propose a new model to identify novel classes, namely, Detection of Novel Classes (DNC). The proposed method adopts long short term memory to continuously observe the streaming data in order to detect emerging classes. The continuous monitoring allows the model to distinguish between existing classes and the novel classes which save time and memory. Also, the proposed method is demonstrated for identifying more than one novel class. The experiments are performed over seven different datasets. The results confirm the efficiency is increased ranging from 6% to 34% by the proposed method in identifying new concepts in the evolving data stream than the existing methods available in the literature.

Recently there has been a growing interest in window joins for scenarios in which data streams arrive at very high rates and a DSMS is registered with many simultaneous queries. Most of the algorithms proposed in the literature are implemented by software. In contrast, we present a novel algorithm named M3Join which can be implemented by software or hardware. M3Join is based on a join architecture which contains a join-routing-table and several half-join architectures. The join architecture is initialized or updated according to the simultaneous queries. Each tuple in the data streams extended with a route tag searches the join-routing-table and switches into the proper half-join architecture to perform join operations or return to end users. The generated join tuples whose route tags have been updated iterate the above search and join procedures until there is no join tuples produced. The algorithm needs only one scan over the data streams since different join queries share the intermediate results. The FPGA implementation of M3Join is presented in detail. The experimental results show that the algorithm is effective and hardware can accelerate join processing vastly.

Recent emerging applications, such as network traffic analysis, web click stream mining, power consumption measurement, sensor network data analysis, and dynamic tracing of stock fluctuation, call for study of a new kind of data, stream data. Many data stream management systems, prototype systems and software components have been developed to manage the streams or extract knowledge from stream data. Mining frequent patterns is a foundational job for the methods of data mining and knowledge discovery. This paper proposes an algorithm for mining the recent frequent patterns over an online data stream. This method uses RFP-tree to store compactly the recent frequent patterns of a stream. The content of each transaction is incrementally updated into the pattern tree upon its arrival by scanning the stream only once. Moreover, the strategy of conservative computation and time decaying model are used to ensure the correctness of the mining results. Finally, the performance results of extensive simulation show that our work can reduce the average processing time of stream data element and it is superior to other analogous algorithms.

Providing efficient mining algorithm to discover recent frequent XML user query patterns is crucial, as many applications use XML to represent data in their disciplines over the Internet. These recent frequent XML user query patterns can be used to design an index mechanism or cached and thus enhance XML query performance. Several XML query pattern stream mining algorithms have been proposed to record user queries in the system and thus discover the recent frequent XML query patterns over a stream. By using these recent frequent XML query patterns, the query performance of XML data stream is improved. In this paper, user queries are modeled as a stream of XML queries and the recent frequent XML query patterns are thus mined over the stream. Data-stream mining differs from traditional data mining since its input of mining is data streams, while the latter focuses on mining static databases. To facilitate the one-pass mining process, novel schemes (i.e. XstreamCode and XstreamList) are devised in the mining algorithm (i.e. X²StreamMiner) in this paper. X²StreamMiner not only reduces the memory space, but also improves the mining performance. The simulation results also show that X²StreamMiner algorithm is both efficient and scalable. There are two major contributions in this paper. First, the novel schemes are proposed to encode and store the information of user queries in an XML query stream. Second, based on the two schemes, an efficient XML query stream mining algorithm, X²StreamMiner, is proposed to discover the recent frequent XML query patterns.

We study the problem of maintaining a (1 + ∊)-factor approximation of the diameter of a stream of points under the sliding window model. In one dimension, we give a simple algorithm that only needs to store points at any time, where the parameter R denotes the "spread" of the point set. This bound is optimal and improves Feigenbaum, Kannan, and Zhang's recent solution by two logarithmic factors. We then extend our one-dimensional algorithm to higher constant dimensions and, at the same time, correct an error in the previous solution. In high nonconstant dimensions, we also observe a constant-factor approximation algorithm that requires sublinear space. Related optimization problems, such as the width, are also considered in the two-dimensional case.

A burst is an unusually large number of events occurring within a certain period of time. Various burst analysis methods over multiple window size have been proposed. However, real-time burst analysis is difficult owing to the huge amount of computation. This article proposes a method to analyze a burst in real-time. The proposed method reduces computation by avoiding redundant data updates of no event occurrence, and by suppressing data within a certain period in the case of emergent increase of events. In addition, a level and a rank of a burst can be analyzed simultaneously. The effectiveness of the proposed method is evaluated by experiments with real data. The result shows that the proposed method is more effective in analyzing real data, and more efficient in handling a large amount of events.

In recent years, tremendous amounts of data streams are generated in different application areas. The new challenges in these data need fast and online data processing, especially in classification problems. One of the most challenging problems in field of data streams that reduces the performance of traditional methods is concept change. To handle this problem, it is necessary to update the classifier system after every alteration of the concept of data. However, updating a classifier can often be a time consuming and expensive process. In this paper, an efficient method is proposed for quickly and easily updating of a fuzzy rule-based classifier by setting a weight for each rule. Then, two online procedures for online adjustment of the rule weights are proposed. The experimental results show the high performance of these methods against a non-weighted approach.

Mining is a challenging and important task in a non-stationary data stream. It is used in financial sectors, web log analysis, sensor networks, network traffic management, etc. In this environment, data distribution may change overtime and is called concept drift. So, it is necessary to identify the changes and address them to keep the model relevant to the incoming data. Many researchers have used Drift Detection Method (DDM). However, DDM is very sensitive to detect gradual drift where the detection delay is high. In this paper, we propose Adaptive Drift Detection Method (ADDM) which improves the performance of the drift detection mechanism. The ADDM uses a new parameter to detect the gradual drift in order to reduce the detection delay. The proposed method, ADDM, experiments with six synthetic datasets and four real-world datasets. Experimental results confirm that ADDM reduces the drift detection delay and false-positive rate (FPR) while preserving high classification accuracy.

Multiple data streams learning has attracted high attention recently. However, different feature spaces and uncertain concept drift situations among each stream may lead to the learning decay of machine learning models. To address this issue, this chapter proposes an adaptive stacking method for multiple data stream learning. First, a stacking-based learning framework is built to handle multiple data streams with different feature spaces. Second, a selective retraining scheme is developed for concept drift adaptation. Finally, by testing the proposed method on five data scenarios and comparing it with three benchmarks, the experiment results show the efficiency.

Frequent items detection is a very useful technique in many applications, such as network monitor, network intrusion detection, worm virus detection, and so on, where data is generally uncertain and could be described using probability. While having been studied intensively in the field of deterministic data, frequent items detection is still novel in the emerging uncertain data field. In this paper, we study the semantic of frequent items detection on uncertain data stream and present a new definition of frequent items over sliding window. Based on the definition, an efficient algorithm is proposed to detect frequent items on uncertain data stream. The algorithm finds the recursion rule in probability computation and greatly improves the efficiency of single data detection, and dynamically detects recent m elements incrementally. Finally, detailed analysis and thorough experimental results demonstrate the efficiency and scalability of our approach.