INTEL RESEARCH SEMINAR

DATE: Thursday, January 11, 2005
TIME: 10.30 am – 12.00 noon
PLACE: Intel Seminar (417 S. Craig Street - 3rd Floor)
INTEL EVENTS PAGE: http://www.intel-research.net/pittsburgh/events.htm

SPEAKER:
Rajmohan Rajaraman
Northeastern University

TITLE:
Algorithms for Multi-Query Processing in Sensor Networks

ABSTRACT:
A powerful database abstraction for sensor networks has recently emerged in which clients program the sensors using a declarative query language, permitting the system to perform low-level optimizations for effective query processing. This talk concerns the energy-efficient processing of multiple aggregate queries in sensor networks.

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.

BIO:
Professor Rajaraman's primary research area is distributed and parallel algorithms, with an emphasis on the design and analysis of algorithms for data management, load balancing, routing, and scheduling in distributed networks. Currently, he is involved in three research projects: (1) the design of efficient schemes for data organization and retrieval in distributed networks; (2) a study of multiconstrained optimization problems arising in network routing and design; and (3) the design of competitive online scheduling algorithms, with applications to Web servers.

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.

For Further Seminar Info:
Contact Kim Kaan, 412-605-1203, or visit http://www.intel-research.net.

SDI / LCS Seminar Questions?
Karen Lindenfelser, 86716, or visit www.pdl.cmu.edu/SDI/