John Byers (Boston University) - Approximate Aggregation Techniques for Sensor Databases
Date: June 25th 2004, 10:30am

Room: C044


In the emerging area of sensor-based systems, a significant challenge isto develop scalable, fault-tolerant methods to extract useful informationfrom the data the sensors collect.An approach to this data management problem is the use of sensordatabases, exemplified by TinyDB and Cougar, which allow users to performaggregation queries such as MIN, COUNT and AVG on a sensor network. Robuststrategies for handling aggregation queries must address the issues ofpacket loss, node failures and power constraints that are inherent in sucha system. To this end, we investigate the use of approximate, in-networkaggregation techniques using small, duplicate-insensitive sketches.In-network aggregation and the use of sketches keeps power consumed bymessage transmission in check, while duplicate-insensitivity enablesfault-tolerant dispersity routing of sketched aggregates.The talk will place equal weight on theoretical foundations andexperimental evaluation. The former includes taking Flajolet-Martinsketches for COUNT and extending them to SUM and AVG, and applyingWalker's elegant method for sampling from an arbitrary discrete pdf inO(1) time. Experimental evaluation involves validation of our approach inthe TAG simulator.Joint work with Jeffrey Considine, George Kollios and Feifei Li.


John W. Byers is Assistant Professor of Computer Science at BostonUniversity and Affiliated Scientist at Digital Fountain, Inc. Prior tojoining B.U., he completed his Ph.D. in Computer Science at the Universityof California at Berkeley in 1997 and was a post-doctoral researcher atthe International Computer Science Institute in Berkeley in 1998. Hisresearch interests include algorithmic aspects of networking, Internetcontent delivery, and network measurement.Dr. Byers received a National Science Foundation CAREER Award in 2001, andthe IEEE ICDE Best Paper Award in 2004. He serves on the editorial boardof IEEE/ACM Transactions on Networking, and is active on the programcommittees for numerous top conferences, including ACM SIGCOMM, ACMSIGMETRICS, and IEEE INFOCOM.