Lightweight monitoring of distributed streams

Arnon Lazerson, Daniel Keren, Assaf Schuster

نتاج البحث: فصل من :كتاب / تقرير / مؤتمرمنشور من مؤتمرمراجعة النظراء

ملخص

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 advantageous to deffne 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 exceedingly heavy computational burden at the nodes, which renders it very problematic to apply, especially for "thin", battery-operated sensors, which are prevalent in numerous applications, including the "Internet of Things" paradigm. Here we propose a very different approach, designated CB (for Convex/Concave Bounds). CB is based on directly bounding the monitored function by suitably chosen convex and concave functions, that naturally enable monitoring distributed streams. These functions can be checked on the fly, yielding far simpler local conditions than those applied by GM. CB's superiority over GM is demonstrated in reducing computational complexity, by several orders of magnitude in some cases. As an added bonus, CB also reduced communi- cation overhead in all application scenarios we tested.

اللغة الأصليةإنجليزيّة أمريكيّة
عنوان منشور المضيفKDD 2016 - Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
الصفحات1685-1694
عدد الصفحات10
رقم المعيار الدولي للكتب (الإلكتروني)9781450342322
المعرِّفات الرقمية للأشياء
حالة النشرنُشِر - 13 أغسطس 2016
الحدث22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2016 - San Francisco, الولايات المتّحدة
المدة: ١٣ أغسطس ٢٠١٦١٧ أغسطس ٢٠١٦

سلسلة المنشورات

الاسمProceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
مستوى الصوت13-17-August-2016

!!Conference

!!Conference22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD 2016
الدولة/الإقليمالولايات المتّحدة
المدينةSan Francisco
المدة١٣/٠٨/١٦١٧/٠٨/١٦

All Science Journal Classification (ASJC) codes

  • !!Software
  • !!Information Systems

بصمة

أدرس بدقة موضوعات البحث “Lightweight monitoring of distributed streams'. فهما يشكلان معًا بصمة فريدة.

قم بذكر هذا