---
_id: '7348'
abstract:
- lang: eng
  text: '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. '
alternative_title:
- LIPIcs
article_number: '20'
article_processing_charge: No
arxiv: 1
author:
- first_name: Thomas
  full_name: Ferrere, Thomas
  id: 40960E6E-F248-11E8-B48F-1D18A9856A87
  last_name: Ferrere
  orcid: 0000-0001-5199-3143
- first_name: Thomas A
  full_name: Henzinger, Thomas A
  id: 40876CD8-F248-11E8-B48F-1D18A9856A87
  last_name: Henzinger
  orcid: 0000−0002−2985−7724
- first_name: Bernhard
  full_name: Kragl, Bernhard
  id: 320FC952-F248-11E8-B48F-1D18A9856A87
  last_name: Kragl
  orcid: 0000-0001-7745-9117
citation:
  ama: 'Ferrere T, Henzinger TA, Kragl B. Monitoring event frequencies. In: <i>28th
    EACSL Annual Conference on Computer Science Logic</i>. Vol 152. Schloss Dagstuhl
    - Leibniz-Zentrum für Informatik; 2020. doi:<a href="https://doi.org/10.4230/LIPIcs.CSL.2020.20">10.4230/LIPIcs.CSL.2020.20</a>'
  apa: 'Ferrere, T., Henzinger, T. A., &#38; Kragl, B. (2020). Monitoring event frequencies.
    In <i>28th EACSL Annual Conference on Computer Science Logic</i> (Vol. 152). Barcelona,
    Spain: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href="https://doi.org/10.4230/LIPIcs.CSL.2020.20">https://doi.org/10.4230/LIPIcs.CSL.2020.20</a>'
  chicago: Ferrere, Thomas, Thomas A Henzinger, and Bernhard Kragl. “Monitoring Event
    Frequencies.” In <i>28th EACSL Annual Conference on Computer Science Logic</i>,
    Vol. 152. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020. <a href="https://doi.org/10.4230/LIPIcs.CSL.2020.20">https://doi.org/10.4230/LIPIcs.CSL.2020.20</a>.
  ieee: T. Ferrere, T. A. Henzinger, and B. Kragl, “Monitoring event frequencies,”
    in <i>28th EACSL Annual Conference on Computer Science Logic</i>, Barcelona, Spain,
    2020, vol. 152.
  ista: '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.'
  mla: Ferrere, Thomas, et al. “Monitoring Event Frequencies.” <i>28th EACSL Annual
    Conference on Computer Science Logic</i>, vol. 152, 20, Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik, 2020, doi:<a href="https://doi.org/10.4230/LIPIcs.CSL.2020.20">10.4230/LIPIcs.CSL.2020.20</a>.
  short: T. Ferrere, T.A. Henzinger, B. Kragl, in:, 28th EACSL Annual Conference on
    Computer Science Logic, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
conference:
  end_date: 2020-01-16
  location: Barcelona, Spain
  name: 'CSL: Computer Science Logic'
  start_date: 2020-01-13
date_created: 2020-01-21T11:22:21Z
date_published: 2020-01-15T00:00:00Z
date_updated: 2021-01-12T08:13:12Z
day: '15'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.4230/LIPIcs.CSL.2020.20
external_id:
  arxiv:
  - '1910.06097'
file:
- access_level: open_access
  checksum: b9a691d658d075c6369d3304d17fb818
  content_type: application/pdf
  creator: bkragl
  date_created: 2020-01-21T11:21:04Z
  date_updated: 2020-07-14T12:47:56Z
  file_id: '7349'
  file_name: main.pdf
  file_size: 617206
  relation: main_file
file_date_updated: 2020-07-14T12:47:56Z
has_accepted_license: '1'
intvolume: '       152'
language:
- iso: eng
month: '01'
oa: 1
oa_version: Published Version
project:
- _id: 25F2ACDE-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: S11402-N23
  name: Rigorous Systems Engineering
- _id: 25F42A32-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: Z211
  name: The Wittgenstein Prize
publication: 28th EACSL Annual Conference on Computer Science Logic
publication_identifier:
  isbn:
  - '9783959771320'
  issn:
  - 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: 1
status: public
title: Monitoring event frequencies
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 152
year: '2020'
...