Thursday, January 11, 2005
NOTE SPECIAL DAY AND TIME
We consider a sensor network in which queries are issued through a special gateway node, sensor data are processed within the network and the results propagated to the gateway. In the first part of the talk, we assumed a fixed aggregation schedule (tree) and present new techniques for encoding the results of query computations, aimed at minimizing the communication cost for processing multiple aggregate queries. In the second part, we present an algorithm for computing an aggregation schedule (tree) that simultaneously well-approximates the communication cost for every possible query. In obtaining this result, we have developed a new notion of universal approximation, which has diverse applications and is of independent interest.
Professor Rajaraman earned his PhD in December 1997. His dissertation concerned resource sharing in distributed systems. In it, he demonstrated that a number of basic resource-sharing problems admit efficient solutions in the form of simple local algorithms. Before joining the College of Computer Science in fall 1998, Professor Rajaraman was a postdoctoral fellow at the National Science Foundation's Center for Discrete Mathematics and Theoretical Computer Science. His work included study of a class of facility-location problems, applicable in such diverse fields as telecommunications, public policy, and information retrieval. With other researchers, he showed that a simple local-search heuristic yields near-optimal solutions to several facility-location problems.
SDI Home: http://www.pdl.cmu.edu/SDI/