The Taub Faculty of Computer Science Events and Talks

As data becomes dynamic, large, and distributed, there is increasing demand for what have become known as distributed stream algorithms. Since continuously collecting the data to a central server and processing it there incurs very high communication and computation complexities, it is desirable to define local conditions at the nodes, such that - as long as they are maintained - some desirable global condition holds. A generic algorithm which proved very useful for reducing communication in distributed streaming environments is geometric monitoring (GM). Alas, applying GM to many important tasks is computationally very demanding, as it requires solving a notoriously difficult problem - computing the distance between a point and a surface, which is often very time consuming even in low dimensions. Thus, while useful for reducing communication, GM often suffers from heavy computational burden at the nodes. Here we propose a very different approach, designated CB (for Convex/Concave Bounds), which is based on directly bounding the monitored function by suitably chosen convex and concave functions. In a nutshell, we work with functions, which can be checked on the fly, whereas GM works with sets and has to test complicated geometric conditions. We demonstrate CB's superiority over GM in reducing computational complexity, which is lower by orders of magnitude in some cases. As an added bonus, CB also reduced communication overhead in all application scenarios we tested. We also show that every solution arrived at by GM is realizable in CB.