Regular Programming over Data Streams

Опубликовано 30 июня 2016, 18:37

The problem of programming stream transformations is becoming increasingly important with the emergence of large data streams such as from sensors, internet routers, and gene sequences. Many monitoring queries---for example, what is the average number of packets transmitted by a router per second---and policy actions depend on temporal properties, such as recognizing certain patterns of events, and iteratively aggregating results from these patterns. In this presentation, I will describe the model of quantitative regular expressions (QREs), a simple formalism to conveniently express such queries. Starting with a small set of base functions, QREs are built using function combinators such as choice, concatenation, and iteration, similar to how regular expressions are combined using union, concatenation and Kleene-*. The framework is parameterized by the cost operations of interest, such as max, min, sum, average and rank, and even generalizes to non-numerical output domains such as strings. Appropriate expressiveness results hold as a function of the chosen cost operations. QREs are an exciting framework because they have a well-understood theory, and can be easily compiled into fast streaming evaluation algorithms. In many cases, memory usage is bounded by a constant, and in some other cases, accurate queries can be automatically converted into approximate function evaluators. I will conclude by describing potential applications in monitoring cyber-physical systems and other data stream sources and future work into automatically parallelizing stream queries.