Shared Hierarchical Aggregation for Monitoring Distributed Streams

Sailesh Krishnamurthy and Michael J. Franklin

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-05-1381
October 2005

http://www.eecs.berkeley.edu/Pubs/TechRpts/2005/CSD-05-1381.pdf

Widely dispersed monitoring networks generate huge data volumes that are naturally organized via hierarchical aggregation. In a system that manages such data, applications pose periodic aggregate queries. In this paper we show how to efficiently process multiple periodic aggregate queries in a hierarchy. First, we use a novel query rewrite that optimally executes individual queries. Next, we show how to combine the rewritten queries to share computation and communication resources. Finally, we identify a challenge in shared aggregation across a heterogenous hierarchy, namely that push-down reduces sharing and pull-up increases communication. We then propose a "partial push-down" technique that permits effective sharing without increasing communication costs.


BibTeX citation:

@techreport{Krishnamurthy:CSD-05-1381,
    Author = {Krishnamurthy, Sailesh and Franklin, Michael J.},
    Title = {Shared Hierarchical Aggregation for Monitoring Distributed Streams},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {2005},
    Month = {Oct},
    URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/2005/6508.html},
    Number = {UCB/CSD-05-1381},
    Abstract = {Widely dispersed monitoring networks generate huge data volumes that are naturally organized via hierarchical aggregation. In a system that manages such data, applications pose periodic aggregate queries. In this paper we show how to efficiently process multiple periodic aggregate queries in a hierarchy. First, we use a novel query rewrite that optimally executes individual queries. Next, we show how to combine the rewritten queries to share computation and communication resources. Finally, we identify a challenge in shared aggregation across a heterogenous hierarchy, namely that push-down reduces sharing and pull-up increases communication. We then propose a "partial push-down" technique that permits effective sharing without increasing communication costs.}
}

EndNote citation:

%0 Report
%A Krishnamurthy, Sailesh
%A Franklin, Michael J.
%T Shared Hierarchical Aggregation for Monitoring Distributed Streams
%I EECS Department, University of California, Berkeley
%D 2005
%@ UCB/CSD-05-1381
%U http://www.eecs.berkeley.edu/Pubs/TechRpts/2005/6508.html
%F Krishnamurthy:CSD-05-1381