1 Search Results for "Garofalakis, Minos"

Document

DOI: 10.4230/LIPIcs.ICDT.2017.14

Distributed Query Monitoring through Convex Analysis: Towards Composable Safe Zones

Authors: Minos Garofalakis and Vasilis Samoladas

Published in: LIPIcs, Volume 68, 20th International Conference on Database Theory (ICDT 2017)

Abstract

Continuous tracking of complex data analytics queries over high-speed distributed streams is becoming increasingly important. Query tracking can be reduced to continuous monitoring of a condition over the global stream. Communication-efficient monitoring relies on locally processing stream data at the sites where it is generated, by deriving site-local conditions which collectively guarantee the global condition. Recently proposed geometric techniques offer a generic approach for splitting an arbitrary global condition into local geometric monitoring constraints (known as "Safe Zones"); still, their application to various problem domains has so far been based on heuristics and lacking a principled, compositional methodology. In this paper, we present the first known formal results on the difficult problem of effective Safe Zone (SZ) design for complex query monitoring over distributed streams. Exploiting tools from convex analysis, our approach relies on an algebraic representation of SZs which allows us to: (1) Formally define the notion of a "good" SZ for distributed monitoring problems; and, most importantly, (2) Tackle and solve the important problem of systematically composing SZs for monitored conditions expressed as Boolean formulas over simpler conditions (for which SZs are known); furthermore, we prove that, under broad assumptions, the composed SZ is good if the component SZs are good. Our results are, therefore, a first step towards a principled compositional solution to SZ design for distributed query monitoring. Finally, we discuss a number of important applications for our SZ design algorithms, also demonstrating how earlier geometric techniques can be seen as special cases of our framework.

Cite as

Minos Garofalakis and Vasilis Samoladas. Distributed Query Monitoring through Convex Analysis: Towards Composable Safe Zones. In 20th International Conference on Database Theory (ICDT 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 68, pp. 14:1-14:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{garofalakis_et_al:LIPIcs.ICDT.2017.14,
  author =	{Garofalakis, Minos and Samoladas, Vasilis},
  title =	{{Distributed Query Monitoring through Convex Analysis: Towards Composable Safe Zones}},
  booktitle =	{20th International Conference on Database Theory (ICDT 2017)},
  pages =	{14:1--14:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-024-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{68},
  editor =	{Benedikt, Michael and Orsi, Giorgio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2017.14},
  URN =		{urn:nbn:de:0030-drops-70665},
  doi =		{10.4230/LIPIcs.ICDT.2017.14},
  annote =	{Keywords: distributed data streams, geometric method}
}

Refine by Author
1 Garofalakis, Minos
1 Samoladas, Vasilis

Refine by Classification

Refine by Keyword
1 distributed data streams
1 geometric method

Refine by Type
1 document

Refine by Publication Year
1 2017

1 Search Results for "Garofalakis, Minos"

Distributed Query Monitoring through Convex Analysis: Towards Composable Safe Zones

Abstract

Cite as

Thanks for your feedback!

Could not send message