Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

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