Euronetlab-RP
Approximate Aggregation Techniques for Sensor Databases
Vendredi 25 juin 2004John Byers
In the emerging area of sensor-based systems, a significant challenge is to develop scalable, fault-tolerant methods to extract useful information from the data the sensors collect. An approach to this data management problem is the use of sensor databases, exemplified by TinyDB and Cougar, which allow users to perform aggregation queries such as MIN, COUNT and AVG on a sensor network. Robust strategies for handling aggregation queries must address the issues of packet loss, node failures and power constraints that are inherent in such a system. To this end, we investigate the use of approximate, in-network aggregation techniques using small, duplicate-insensitive sketches. In-network aggregation and the use of sketches keeps power consumed by message transmission in check, while duplicate-insensitivity enables fault-tolerant dispersity routing of sketched aggregates. The talk will place equal weight on theoretical foundations and experimental evaluation. The former includes taking Flajolet-Martin sketches for COUNT and extending them to SUM and AVG, and applying Walker's elegant method for sampling from an arbitrary discrete pdf in O(1) time. Experimental evaluation involves validation of our approach in the TAG simulator. Joint work with Jeffrey Considine, George Kollios and Feifei Li.
Bio: John W. Byers is Assistant Professor of Computer Science at Boston University and Affiliated Scientist at Digital Fountain, Inc. Prior to joining B.U., he completed his Ph.D. in Computer Science at the University of California at Berkeley in 1997 and was a post-doctoral researcher at the International Computer Science Institute in Berkeley in 1998. His research interests include algorithmic aspects of networking, Internet content delivery, and network measurement. Dr. Byers received a National Science Foundation CAREER Award in 2001, and the IEEE ICDE Best Paper Award in 2004. He serves on the editorial board of IEEE/ACM Transactions on Networking, and is active on the program committees for numerous top conferences, including ACM SIGCOMM, ACM SIGMETRICS, and IEEE INFOCOM.
Plus d'informations ici …
clementine.said (at) nulllip6.fr