Random Sampling over Streaming Window Joins

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.