Load Shedding for Window Joins over Streams

We address severalload shedding techniques over sliding window joins. We firstconstruct a dual window architectural model including aux-windowsand join-windows, and build statistics on aux-windows. With thestatistics, we develop an effective load shedding strategyproducing maximum subset join outputs. In order to accelerate theload shedding process, binary indexed trees have been utilized toreduce the cost on shedding evaluation. When streams have higharrival rates, we propose an approach incorporating front-sheddingand rear-shedding, and find an optimal trade-off between them. Asfor the scenarios of variable speed ratio, we develop a planreallocating CPU resources and dynamically resizing the windows.In addition, we prove that load shedding is not affected duringthe process of reallocation. Both synthetic and real data are usedin our experiments, and the results show the promise of ourstrategies.