---
res:
bibo_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. @eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: Thomas
foaf_name: Ferrere, Thomas
foaf_surname: Ferrere
foaf_workInfoHomepage: http://www.librecat.org/personId=40960E6E-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0001-5199-3143
- foaf_Person:
foaf_givenName: Thomas A
foaf_name: Henzinger, Thomas A
foaf_surname: Henzinger
foaf_workInfoHomepage: http://www.librecat.org/personId=40876CD8-F248-11E8-B48F-1D18A9856A87
orcid: 0000−0002−2985−7724
- foaf_Person:
foaf_givenName: Bernhard
foaf_name: Kragl, Bernhard
foaf_surname: Kragl
foaf_workInfoHomepage: http://www.librecat.org/personId=320FC952-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0001-7745-9117
bibo_doi: 10.4230/LIPIcs.CSL.2020.20
bibo_volume: 152
dct_date: 2020^xs_gYear
dct_isPartOf:
- http://id.crossref.org/issn/1868-8969
- http://id.crossref.org/issn/9783959771320
dct_language: eng
dct_publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik@
dct_title: Monitoring event frequencies@
...