Search

Join queries over wireless sensor data streams need to be processed immediately to keep up with the input streams. Many existing algorithms do not solve the problem in context of both limited CPU and memory resources. In this paper, we propose two CML statistic model based approximate sliding window multi-joins algorithms for the system that both CPU and memory is limited, and a maximum subset of the exact multi-join result is obtained. To shed the load effectively and produce as many join results as possible with the limited amount of resources, both the statistical information of join attributes value of each stream and the relationship between CPU and memory resource is completely considered. The CML statistic model is designed for obtaining and maintaining the statistical information dynamically. With the model, semantic load shedding algorithms are proposed over streaming sliding window multi-join under both limited CPU and memory resource. And a maximizing multi-join output can be generated without delay. Experimental results show that our approach is more efficient than other approach when both the CPU and memory resource are insufficient to keep pace with input streams.

Two novel sampling approaches are proposed to obtain a random sample of exact streaming window join result. Without assuming any model of stream arrivals, the frequency of join attribute values for various basic periods can be obtained by a frequency balanced binary tree histogram (FATH) which is constructed for each stream. The frequency for the future window can be computed by linear regression with the help of the information in the FATH. With the random sample of exact join result produced, a windowed aggregate over the exact join results can be unbiasedly and accurately estimated. Experimental results show that our approach is more efficient than other approach for arbitrary streams.

Join operator has become more and more important in the context of data stream. Most join algorithms over streams to date are based on nested loop joins or hash joins. However, these time expensive algorithms can not suit for CPU-limited case. In this paper, a clustering-based variable-width histogram is designed for obtaining value distribution of tuples in the sliding windows, and some important characteristics of tuples can be retained. Semi-hash tables can be constructed by using the histogram. Our sliding window semi-hash multi-join algorithm can minimize the processing time cost of join and produce an accurate join result much earlier. Experimental results show that our approach is more efficient than other approaches.

We present a novel clustering-based indexing load shedding technique for sliding window joins (CILS). When the details of the distribution of streams are unknown, to obtain the statistics of data, we dynamically maintain a dual indices model (CRA-index and CCRA-index) for each sliding window. The indices are constructed and maintained by clustering technique, and the locality of data is retained. When CPU capacity is insufficient, our index-based load shedding technique is used by utilizing the CRA-index and CCRA-index, a part of tuples are selected and are kept from performing probing, and finally maximum subset join outputs are produced. The indices are space (a fixed amount of memory is used) and time efficient. Experimental results on synthetic and real life data show that our index-based load shedding approach obtains max-subset results effectively, and outperforms the existing load shedding strategies under the same conditions.

We present a novel load shedding technique, called range loading shedding (denoted as RANGE), for sliding window joins when CPU capacity is insufficient in the system and the details of the distribution of streams are unknown. To obtain the statistics of data, we dynamically maintain clustering range histogram (CR-histogram) and average density counter table (ADC-table) for each sliding window. The CR-Histogram is constructed and maintained by clustering technique with a fixed amount of memory. When CPU capacity is insufficient, the RANGE technique is used to select tuples to be processed by utilizing the CR-Histogram and ADC-table, and then produces maximum subset join outputs. Experimental results on synthetic and real life data show that Range load shedding approach obtains max-subset results effectively, and outperforms the existing load shedding strategies.