Research Scientist - Assaf schuster

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