Window-aware loading shedding (Main contributions ( Regardless of where…
Window-aware loading shedding
queries consisting of one or more aggregate operators with sliding win- dows
This operator / WD is aware of the window properties (size, slide)
Divides the input stream into windows and probabilistically decides which windows to drop
New type of operators called "Window-Drop"/WD
This decision is further encoded into tuples by marking the ones that are disallowed from starting new windows
How new is WD comparing to old approaches?
WD preserves integrity of windows throughout a query plan
always delivers subsets of original query answers with minimal degradation in result quality
2 commons models in the past
model 1: producing approximate answers by omitting tuples from the correct answer
model1's limit: The challenge here is to provide the largest possible subset
model 2: degrading the result is to emit nearly the same number of tuples, each of which might be in- accurate
model 2's limit: The challenge in this case is to ensure that the errors are bounded by some amount. It is an application-level decision as to whether it is better to have all values, some of which may be inaccurate, or fewer values, all of which are accurate
Regardless of where the aggregates appear in a query plan, our approach enables pushing drops across them, to early points in the plan, maximizing the amount of processing saved.
We mathematically analyze the correctness and performance of our approach.
Our technique is general enough to handle arbitrary (user- defined) aggregate functions, multiple levels of aggregate nest- ing, and shared query plans.
We experimentally evaluate the performance of our approach on a stream processing system prototype.
Propose a novel load shedding approach for windowed aggregation queries which guarantees to deliver subset re- sults.