Sliding-window aggregation is important in analyzing data streams, but it seriously suffers from out-of-order streams, which contain late events. The existing approaches are not efficient because they are dependent on the window size. They ignore the past windows affected by the late records. This paper proposes two solutions: (1) CMiX for computing the current window, and (2) PWiX for updating the past windows. Experiments show that CMiX and PWiX can deal with out-of-order streams significantly better than other approaches.

Sliding-window aggregation is one of the core operations in processing and analyzing data streams, but it seriously suffers from the unordered events or elements from data streams. Unordered streams or out-of-order data streams contain events whose order based on their timestamps (called event time) is different from the order based on their arriving times to the system (called ingestion time). Out-of-order data streams typically occur in a distributed environment due to many factors, such as network disruptions and delays. Out-of-order data streams drastically make the processing speed slower and existing works, that can handle out-of-order streams, do not address this problem well and can be further improved. The time complexities of existing approaches are not efficient because they are dependent on$n$, which is the number of slides in the window. In addition, they ignore the past windows affected by the late-arrival records. In many applications, updating and reporting the results of the past windows affected by the late-arrival records in real time is strongly needed. This paper proposes two solutions: (1) A Maximum-allowed lateness-based IndeXing algorithm with a Constant time complexity (CMiX) for computing the current window, and (2) A Past Window Indexing algorithm (PWiX) for efficient updating the past windows. Experimental results show that CMiX and PWiX can deal with out-of-order data streams significantly better than other existing approaches. CMiX is about 3.21 times faster than the state-of-the-art approach by significantly using less memory. It is important to emphasize that all approaches mentioned in the paper have the following limitations: (1) Aggregation can be both distributive and algebraic, which must be commutative due to the out-of-order of data streams, and (2) The window and slide sizes are assumed to be fixed, and if they are changed, the indices must be reconstructed.

Predicting missing attribute values in data is extremely important in improving the accuracy in many applications. Existing algorithms ignore the difference between the records used for learning and predicting. The accuracy is not good enough and can be further improved. This paper proposes two solutions: (1) Maximization-based approach (MP) and (2) Distance-ratio-based approach (DP). MP and DP ensure that the incomplete records with the missed values are similar to the records used to learn the parameters as much as possible. MP and DP learn all possible parameters not only from the k nearest neighboring set (k-NN) but from the k-Sets, which are all possible combinations of k complete records. The parameters learnt from the records that are most similar to the repaired candidates of the incomplete records are chosen. Experimentally, MP and DP significantly outperform the existing approaches.

Stream processing is used in various fields. In the field of big data, stream aggregation is a popular processing technique, but it suffers serious setbacks when the order of events (e.g., stream elements) occurring is different from the order of events arriving to the systems. Such data streams are called "non-FIFO steams". This phenomenon usually occurs in a distributed environment due to many factors, such as network disruptions, delays, etc. Many analyzing scenarios require efficient processing of such non-FIFO streams to meet various data processing requirements. This paper proposes an efficient scalable checkpoint-based bidirectional indexing approach, called CPiX , for faster real-time analysis over non-FIFO streams. CPiX maintains the partial aggregation results in an on-demand manner. CPiX needs less time and space than the state-of-the-art approach. Extensive experiments confirm that CPiX can deal with out-of-order streams very efficiently and is, on average, about 3.8 times faster than the state-of-the-art approach while consuming less memory. CPiX and the existing approaches support the distributive and algebraic aggregation functions, such as min, average, standard deviation, etc. Holistic aggregation is beyond the scope.

Stream processing is used in various fields. In the field of big data, stream aggregation is a popular processing technique, but it suffers serious setbacks when the order of events (e.g., stream elements) occurring is different from the order of events arriving to the systems. Such data streams are called “non-FIFO steams”. This phenomenon usually occurs in a distributed environment due to many factors, such as network disruptions, delays, etc. Many analyzing scenarios require efficient processing of such non-FIFO streams to meet various data processing requirements. This paper proposes an efficient scalable checkpoint-based bidirectional indexing approach, called$CPiX$, for faster real-time analysis over non-FIFO streams. CPiX maintains the partial aggregation results in an on-demand manner per checkpoint. CPiX needs less time and space than the state-of-the-art approach. Extensive experiments confirm that CPiX can deal with out-of-order streams very efficiently and is, on average, about 3.8 times faster than the state-of-the-art approach while consuming less memory.

With the rise of Web search engines, processing keyword search over XML and XML streams has drawn much attention from many researchers. Compared to conventional query methods, keyword search has several benefits for its simplicity and its user-friendliness in querying XML databases. Therefore, a great deal of effort has been put on this search paradigm by trying to improve the quality of search result of pure keyword search, where only keywords are allowed as a query. However, due to the vagueness of keyword search, it is hard to accurately express real search intention with just keyword search. We observe that there are many cases where the combination of path-based query and keyword search is a better choice and can deal with such challenge. To address this problem, we propose a method to integrate XPath and keyword search so that users can accurately express their search demands. The experimental results show that the proposed scheme can process queries over XML streams practically.