Research Scientist - Assaf schuster June 14, 2008

Favorite:

Google Tech Talks
June, 13 2008

ABSTRACT

Research Scientist - Assaf schuster

Title: "A Geometric Approach to Detecting Global Properties over Distributed Data"

Abstract:

A basic construct in many distributed systems is the detection of global properties over distributed data.
Examples include a wireless sensor network where we would like to be alerted whenever the average
of the temperature readings taken by the sensors exceeds a given threshold, or a distributed search engine
where the set of search terms whose frequency of use is above a given threshold must be determined.

Until recently, research has focused on detecting global properties that are defined by simple aggregates
(e.g., sum, average, or minimum) over the distributed data. In many cases, however, global properties
of interest are expressed by more complex functions. This is the case, for instance, when the goal is to
detect when the variance in sensor-network readings is in excess of a threshold, or when the set of pairs
of search terms whose correlation exceeds a threshold is to be determined. Such tasks typically require
that all the data be collected to a central location, incurring very high communication costs.

In this talk I present a novel geometric approach for efficiently detecting a wide family of global properties
that are defined by the value of an arbitrary function on the distributed data vis-a-vis a given threshold.
The global property is split into a set of constraints applied locally at each node. As long as the local
constraints at all the nodes are satisfied, the global property is guaranteed to be satisfied as well,
and no communication is required.

I begin by presenting the geometric detection method and show how it is applied for efficient detection
of complex events in a distributed streaming setting. Time permitting, I will also show how it can be
used for determining top-k queries over distributed databases.

Speaker: Research Scientist - Assaf Schuster