Search published articles


Showing 5 results for Data Stream
Providing a Dynamic Technique for Answering Ad-hoc Continuous Aggregate
, Dr. Ali Safaei,
Volume 14, Issue 3 (12-2017)
Abstract
Data Streams are infinite, fast, time-stamp data elements which are received explosively. Generally, these elements need to be processed in an online, real-time way. So, algorithms to process data streams and answer queries on these streams are mostly one-pass. The execution of such algorithms has some challenges such as memory limitation, scheduling, and accuracy of answers. They will be more important and serious, chiefly if the queries are not predefined but Ad-hoc, and also should be executed after data stream tuples are gone.
Countinous aggregate queries are types of queries with some special characteristics making it possible to perform more specific, efficient qeury processing techniques, specifiaclly beneficient for ad-hoc ones.
In this paper, a dynamic efficient techinque is proposed for answering the ad-hoc continiues aggregate queries over data streams. The main idea of the proposed technique is to generate and handle an efficiet tree data structure as the synopse, in the form of  Dynamic Prefix Aggregate Tree.
In general, the two following approaches can be used to calculate any function such as ; either implementation of an algorithm for the calculation of function f, or storing the answers of function f for all possible states. When the algorithm runtime is high, the second method strengthened by proper selection of indices can return a proper answer in a very short time (even ).
But the major problem of the second method is the total number of possible answers which can be very high and also can be out of the possible storage capacity and processing potential within a certain acceptable time period. For example, suppose that the cardinality of each of the parameters of  is 10. In this case, the total number of possible states will be . As it is evident, the total number of states increases with the number of parameters and their cardinalities.When the total number of states is so great that generating answers with respect to consumed time and space is impossible, a more convenient, practical method should be employed. This more practical approach can be the storing of some of the answers (selectively) with respect to the following conditions:
  • Obtaining un-stored answers from the set of stored answers.
  • Higher probability of utilizing stored answers (i.e. higher probability of submitting requests from stored set).
  • Eliminating (not storing) null answers.
The same idea can be implemented for online and almost real time processing of queries, so that by receiving each tuple, all possible answers get obtained and stored. By doing so, in the time of need (when answering to an ad-hoc query) stored answers will be used instead of calculating each answer.
Accordingly, some answers are stored in a tree structure to be used at the right time. In this paper, in order to answer ad-hoc continuous aggregate queries over data streams, a method is proposed that uses a tree structure for storing the aggregate results. The important point in this method is that all steps of the construction, maintenance and using of the tree must be online. For these purposes, it is enough to keep all possible answers. But to apply an online construction and maintenance of tree, we must keep some answers, according to the inherent features of data streams. In this way, the main goal is to choose the answers possessing the most overlap with responses answers of received ad-hoc queries. The proposed method, creates the tree structure and maintains it dynamically to answer ad-hoc aggregate continuous queries over data streams.
For this purpose, queries at instant  are modeled as in form of , where  or  (when , the aggregate over the whole sliding window is returned) and  is the size of sliding window and  (when , the aggregate over the whole  is returned).
In order to increase the overlapping, a statistical task is performed on a dimensions of the received queries. In this way, dimensions are determined with the highest, lowest request. When , means that there is no request for this dimension. Therefore, we select and store the answers related to the dimension with highest request, and ignore those with the lowest. Obviously, these answers should be obtained and presented using stored answers.
As the request for dimensions may change, the tree structure must be dynamically constructed and maintenance that will be presented this dynamic structure in this paper. Experimental evaluattion of the proposed method shows that, using the proposed Dynamic Aggregate Tree for ansering countinous Ad-hoc aggregate queies is more cost-effective, in terms of response time and memory usage.
Improving Near Real Time Data Warehouse Refreshment
Mr. Isa Hazrati, Dr. Negin Daneshpour,
Volume 15, Issue 2 (9-2018)
Abstract
Near-real time data warehouse gives the end users the essential information to achieve appropriate decisions. Whatever the data are fresher in it, the decision would have a better result either. To achieve a fresh and up-to-date data, the changes happened in the side of source must be added to the data warehouse with little delay. For this reason, they should be transformed in to the data warehouse format. One of the famous algorithms in this area is called X-HYBRIDJOIN. In this algorithm the data characteristics of real word have been used to speed up the join operation. This algorithm keeps some partitions, which have more uses, in the main memory. In the proposed algorithm in this paper, disk-based relation is joined with input data stream. The aim of such join is to enrich stream. The proposed algorithm uses clustered index for disk-based relation and join attribute. Moreover, it is assumed that the join attribute is exclusive throughout the relation. This algorithm has improved the mentioned algorithm in two stages. At the first stage, some records of source table which are frequently accessible are detected. Detection of such records is carried out during the algorithm implementation. The mechanism is in the way that each record access is counted by a counter and if it becomes more than the determined threshold, then it is considered as the frequently used record and placed in the hash table. The hash table is used to keep the frequently used records in the main memory. When the stream is going to enter in to join area, it is searched in this table. At the second stage, the choice method of the partition which is going to load in the main memory has been changed. One dimensional array is used to choose the mentioned partition. This array helps to select a partition of source table with highest number of records for the join among all partitions of source table. Using this array in each iteration, always leads to choose the best partition loading in memory. To compare the usefulness of the suggested algorithm some experiments have been done. Experimental results show that the service rate acquired in suggested algorithm is more than the existing algorithms. Service rate is the number of joined records in a time unit. Increasing service rate causes the effectiveness of the algorithm.

Detecting Concept Drift in Data Stream Using Semi-Supervised Classification
Hossein Hasan Nezhad Namaghi, Hoda Mashayekhi, Morteza Zahedi,
Volume 18, Issue 4 (3-2022)
Abstract
Data stream is a sequence of data generated from various information sources at a high speed and high volume. Classifying data streams faces the three challenges of unlimited length, online processing, and concept drift. In related research, to meet the challenge of unlimited stream length, commonly the stream is divided into fixed size windows or gradual forgetting is used. Concept drift refers to changes in the statistical properties of data, and is divided into four categories: sudden, gradual, incremental, and recurring. Concept drift is generally dealt with by periodically updating the classifier, or employing an explicit change detector to determine the update time. These approaches are based on the assumption that the true labels are available for all data samples. Nevertheless, due to the cost of labeling instances, access to a partial labeling is more realistic. In a number of studies that have used semi-supervisory learning, the labels are received from the user to update the models in form of active learning. The purpose of this study is to classify samples in an unlimited data stream in presence of concept drift, using only a limited set of initial labeled data. To this end, a semi-supervised ensemble learning algorithm for data stream is proposed, which uses entropy variation to detect concept drift and is applicable for sudden and gradual drifts. The proposed model is trained with a limited initial labeled set. In occurrence of concept drift, the unlabeled data is used to update the ensemble model. It does not require receiving the labels from the user. In contrast to many of the current studies, the proposed algorithm uses an ensemble of K-NN classifiers. It constructs a group of clustering-based classification models, each of which is trained on a batch of data. On receiving each new sample, first it is determined whether the data sample is an outlier or not. If the data is included in a cluster, the sample class is determined by majority voting. When a window of the stream is received, the possibility of concept drift is examined based on entropy variation, and the classifier is updated by a semi-supervised approach if necessary. The model itself determines the required data labels. The proposed method is capable of detecting concept drift in data, and improving its accuracy via updating the learning model with appropriate samples received from the stream. Therefore, the proposed method only requires a small initial labeled data. Experiments are performed using five real and synthetic datasets, and the model performance is compared to three other approaches. The results show that the proposed method is superior in terms of precision, recall and F1 score compared to other studies.

Outlier Detection on Data Streams Using a QLattice-based Model and Online Learning
Sahar Fardin, Mahdi Hashemzadeh,
Volume 20, Issue 2 (9-2023)
Abstract
With the advancement of computer science, the dramatic developments in data mining area and their increasing applications, the identification of outlier or anomaly data has also become one of the most important research topics. In most applications, the outlier data contain beneficial information that can be used to gain useful knowledge. Today, there are a large number of applications on data streams, in the vast majority of which the discovery of outlier/anomaly data is very important and in some cases vital. Detection of anomalies is an important way for detecting frauds, network intrusion detection, detection of abnormal behaviors in monitoring systems, and other rare events that are always of great importance; but they are often difficult to identify. Most of the existing efficient outlier detection algorithms have been designed for the static data. While outlier detection is more challenging in data streams, where data are generating continuously and has especial properties such as infinity and transience. In this research, we introduce an approach based on the QLattice classification model, which works based on the quantum computing and performs better in the intended application than other classification methods. Given the possibility of changing the distribution of data over time in streaming data, a scheme to take advantage of online incremental learning is also applied in the proposed method. Considering the unlimited data flow and limited processing memory, the detection process is applied to a window of data that is constantly updated with data sampled from previous windows. A function is also designed to solve the problem of data imbalance, which uses the random sampling technique to solve this issue. The results of experiments obtained on benchmark datasets show that the proposed approach has better performance than other methods.

Online Learning for Imbalanced Data Streams with Concept Drift by Belief Theory and Chaotic Function
Dr. Javad Hamidzadeh, Mohammad Ali Rashidi Mahmoodi, Mona Moradi,
Volume 20, Issue 4 (3-2024)
Abstract
Continual learning from data streams is a pivotal aspect of machine learning, requiring the development of algorithms capable of adapting to incoming data. However, the ongoing evolution of data streams presents a formidable challenge as previously acquired knowledge may become outdated. This challenge, known as concept drift, demands timely detection for the effective adaptation of learning models. While various drift detectors have been proposed, they often assume a relatively balanced class distribution. In scenarios with imbalanced data streams, these detectors may exhibit bias toward majority classes, overlooking shifts in minority classes. Moreover, the imbalance among classes can change over time, with roles shifting between majority and minority classes, especially when relationships among classes become complex due to overlapping regions. In this paper, a novel classification method is introduced for imbalanced streaming data affected by concept drift. The proposed method continuously monitors arriving streams to detect and adapt to both imbalances and concept drift. Upon receiving a new block of data, the proposed method employs the k-means clustering approach to identify non-dense regions and performs oversampling for minority classes. Cluster centers are selected using the belief function to address overlapping issues between majority and minority classes. Utilizing a chaotic approach, the new sample is added based on its neighborhood and the size of thresholds that cover time intervals and classification errors. Finally, the label prediction process is done by ensemble learning and weighted majority voting. Experiments conducted on benchmark datasets from the UCI database evaluate the performance of the proposed method using Leave-One-Out (LOO) validation and comparisons with state-of-the-art methods. The results demonstrate the superiority of the proposed method across various evaluation criteria, highlighting its effectiveness in addressing imbalanced streaming data with concept drift.

Page 1 from 1     

© 2015 All Rights Reserved | Signal and Data Processing