The Taub Faculty of Computer Science Events and Talks

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 receive an alert every time the average of the temperature readings taken by the sensors exceeds a given threshold, or a distributed search engine, where we would like to determine the set of search terms whose frequency of use exceeds a given threshold. Until recently, research has focus 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. Examples include detecting when the variance of the sensor readings in a sensor network exceeds a given threshold, or determining the set of pairs of search terms whose correlation exceeds a given threshold. Resolving such tasks typically requires collecting all the data to a central location, thus incurring very high communication costs. In this talk I present a novel geometric approach that enables efficiently detecting a wide family of global properties, which 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, it is guaranteed that the global property is satisfied as well, and no communication is required. I start by presenting the geometric detection method, and show how it is applied for efficiently detecting complex events in a distributed streaming setting. Next, I show how the geometric detection method can be efficiently employed in a wireless sensor network. Finally, I show how it can be used for determining top-k queries over distributed databases.