Monitoring event frequencies

T. Ferrere, T.A. Henzinger, B. Kragl, in:, 28th EACSL Annual Conference on Computer Science Logic, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, p. 20.

Download
OA 617.21 KB

Conference Paper | Published | English
Department
Series Title
LIPIcs
Abstract
The monitoring of event frequencies can be used to recognize behavioral anomalies, to identify trends, and to deduce or discard hypotheses about the underlying system. For example, the performance of a web server may be monitored based on the ratio of the total count of requests from the least and most active clients. Exact frequency monitoring, however, can be prohibitively expensive; in the above example it would require as many counters as there are clients. In this paper, we propose the efficient probabilistic monitoring of common frequency properties, including the mode (i.e., the most common event) and the median of an event sequence. We define a logic to express composite frequency properties as a combination of atomic frequency properties. Our main contribution is an algorithm that, under suitable probabilistic assumptions, can be used to monitor these important frequency properties with four counters, independent of the number of different events. Our algorithm samples longer and longer subwords of an infinite event sequence. We prove the almost-sure convergence of our algorithm by generalizing ergodic theory from increasing-length prefixes to increasing-length subwords of an infinite sequence. A similar algorithm could be used to learn a connected Markov chain of a given structure from observing its outputs, to arbitrary precision, for a given confidence.
Publishing Year
Date Published
2020-01-15
Proceedings Title
28th EACSL Annual Conference on Computer Science Logic
Volume
152
Article Number
20
Conference
CSL: Computer Science Logic
Conference Location
Barcelona, Spain
Conference Date
2020-01-13 – 2020-01-16
ISSN
IST-REx-ID

Cite this

Ferrere T, Henzinger TA, Kragl B. Monitoring event frequencies. In: 28th EACSL Annual Conference on Computer Science Logic. Vol 152. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2020:20. doi:10.4230/LIPIcs.CSL.2020.20
Ferrere, T., Henzinger, T. A., & Kragl, B. (2020). Monitoring event frequencies. In 28th EACSL Annual Conference on Computer Science Logic (Vol. 152, p. 20). Barcelona, Spain: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.CSL.2020.20
Ferrere, Thomas, Thomas A Henzinger, and Bernhard Kragl. “Monitoring Event Frequencies.” In 28th EACSL Annual Conference on Computer Science Logic, 152:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. https://doi.org/10.4230/LIPIcs.CSL.2020.20.
T. Ferrere, T. A. Henzinger, and B. Kragl, “Monitoring event frequencies,” in 28th EACSL Annual Conference on Computer Science Logic, Barcelona, Spain, 2020, vol. 152, p. 20.
Ferrere T, Henzinger TA, Kragl B. 2020. Monitoring event frequencies. 28th EACSL Annual Conference on Computer Science Logic. CSL: Computer Science Logic, LIPIcs, vol. 152. 20.
Ferrere, Thomas, et al. “Monitoring Event Frequencies.” 28th EACSL Annual Conference on Computer Science Logic, vol. 152, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, p. 20, doi:10.4230/LIPIcs.CSL.2020.20.
All files available under the following license(s):
Creative Commons License:
CC-BYCreative Commons Attribution 4.0 International Public License (CC-BY 4.0)
Main File(s)
File Name
617.21 KB
Access Level
OA Open Access
Last Uploaded
2020-01-21T11:21:04Z


Export

Marked Publications

Open Data IST Research Explorer

Sources

arXiv 1910.06097

Search this title in

Google Scholar
ISBN Search