Ph.D Thesis


Ph.D StudentIzchak Sharfman
SubjectA Geometric Approach to Detecting Global Properties
over Distributed Data
DepartmentDepartment of Computer Science
Supervisor Full Professors Schuster Assaf
Full Thesis textFull thesis text - English Version


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 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 focused on detecting global properties that are defined by simple aggregates over the distributed data. For these cases, there are usually local conditions for the occurrence of the global property of interest. For example, if we have 100 nodes, and we wish to be alerted when the average temperature is over 50 degrees, we can use the observation that for this to occur, the temperature measurement in at least one node has to be over 50 degrees.

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, and determining the set of pairs of search terms whose correlation exceeds a given threshold.

This work studies global properties of the following form: we assume that each node holds a time varying d-dimensional vector. In addition, we assume that we are given an arbitrary scoring function that is evaluated on the average of the local vectors held by the nodes. We are interested in detecting when the value of this function crosses a pre-determined threshold value.

The simplest solution detecting these global properties is for each node to transmit its vector to a central node, which averages the local vectors and evaluates the function at the average. Alas, this solution is prohibitively expensive in terms of communication, and a great deal of research is dedicated to reducing the communication overload.

This work proposes to solve this problem by using a novel geometric approach. It is based on having each node construct a set in the space of data vectors, such that the average vector has to be in at least one of these sets. Then, each node locally checks whether the function's value on its set has crossed the threshold; and if no node issues an alert, there is no need for the nodes to communicate.