Markov Chain Monitoring

Harshal A. Chaudhari, Michael Mathioudakis, Evimaria Terzi

Tutkimustuotos: Artikkeli kirjassa/raportissa/konferenssijulkaisussaKonferenssiartikkeliTieteellinenvertaisarvioitu

Kuvaus

In networking applications, one often wishes to obtain estimates about the number of objects at different parts of the network (e.g., the number of cars at an intersection of a road network or the number of packets expected to reach a node in a computer network) by monitoring the traffic in a small number of network nodes or edges. We formalize this task by defining the Markov Chain Monitoring problem.

Given an initial distribution of items over the nodes of a Markov chain, we wish to estimate the distribution of items at subsequent times. We do this by asking a limited number of queries that retrieve, for example, how many items transitioned to a specific node or over a specific edge at a particular time. We consider different types of queries, each defining a different variant of the Markov Chain Monitoring. For each variant, we design efficient algorithms for choosing the queries that make our estimates as accurate as possible. In our experiments with synthetic and real datasets, we demonstrate the efficiency and the efficacy of our algorithms in a variety of settings.
Alkuperäiskielienglanti
OtsikkoProceedings of the 2018 SIAM International Conference on Data Mining
ToimittajatMartin Ester, Dino Pedreschi
Sivumäärä9
KustantajaSociety for Industrial and Applied Mathematics
Julkaisupäivä2018
Sivut441-449
ISBN (elektroninen)978-1-61197-532-1
DOI - pysyväislinkit
TilaJulkaistu - 2018
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisuussa
TapahtumaSIAM International Conference on Data Mining - San Diego, Yhdysvallat (USA)
Kesto: 3 toukokuuta 20185 toukokuuta 2018
Konferenssinumero: SDM18

Tieteenalat

  • 113 Tietojenkäsittely- ja informaatiotieteet

Lainaa tätä

Chaudhari, H. A., Mathioudakis, M., & Terzi, E. (2018). Markov Chain Monitoring. teoksessa M. Ester, & D. Pedreschi (Toimittajat), Proceedings of the 2018 SIAM International Conference on Data Mining (Sivut 441-449). Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611975321
Chaudhari, Harshal A. ; Mathioudakis, Michael ; Terzi, Evimaria. / Markov Chain Monitoring. Proceedings of the 2018 SIAM International Conference on Data Mining. Toimittaja / Martin Ester ; Dino Pedreschi. Society for Industrial and Applied Mathematics, 2018. Sivut 441-449
@inproceedings{cb5eb1c639494177b737ac20ab75df31,
title = "Markov Chain Monitoring",
abstract = "In networking applications, one often wishes to obtain estimates about the number of objects at different parts of the network (e.g., the number of cars at an intersection of a road network or the number of packets expected to reach a node in a computer network) by monitoring the traffic in a small number of network nodes or edges. We formalize this task by defining the Markov Chain Monitoring problem.Given an initial distribution of items over the nodes of a Markov chain, we wish to estimate the distribution of items at subsequent times. We do this by asking a limited number of queries that retrieve, for example, how many items transitioned to a specific node or over a specific edge at a particular time. We consider different types of queries, each defining a different variant of the Markov Chain Monitoring. For each variant, we design efficient algorithms for choosing the queries that make our estimates as accurate as possible. In our experiments with synthetic and real datasets, we demonstrate the efficiency and the efficacy of our algorithms in a variety of settings.",
keywords = "113 Computer and information sciences",
author = "Chaudhari, {Harshal A.} and Michael Mathioudakis and Evimaria Terzi",
year = "2018",
doi = "10.1137/1.9781611975321",
language = "English",
pages = "441--449",
editor = "Martin Ester and Dino Pedreschi",
booktitle = "Proceedings of the 2018 SIAM International Conference on Data Mining",
publisher = "Society for Industrial and Applied Mathematics",
address = "United States",

}

Chaudhari, HA, Mathioudakis, M & Terzi, E 2018, Markov Chain Monitoring. julkaisussa M Ester & D Pedreschi (toim), Proceedings of the 2018 SIAM International Conference on Data Mining. Society for Industrial and Applied Mathematics, Sivut 441-449, SIAM International Conference on Data Mining, San Diego, Yhdysvallat (USA), 03/05/2018. https://doi.org/10.1137/1.9781611975321

Markov Chain Monitoring. / Chaudhari, Harshal A.; Mathioudakis, Michael; Terzi, Evimaria.

Proceedings of the 2018 SIAM International Conference on Data Mining. toim. / Martin Ester; Dino Pedreschi. Society for Industrial and Applied Mathematics, 2018. s. 441-449.

Tutkimustuotos: Artikkeli kirjassa/raportissa/konferenssijulkaisussaKonferenssiartikkeliTieteellinenvertaisarvioitu

TY - GEN

T1 - Markov Chain Monitoring

AU - Chaudhari, Harshal A.

AU - Mathioudakis, Michael

AU - Terzi, Evimaria

PY - 2018

Y1 - 2018

N2 - In networking applications, one often wishes to obtain estimates about the number of objects at different parts of the network (e.g., the number of cars at an intersection of a road network or the number of packets expected to reach a node in a computer network) by monitoring the traffic in a small number of network nodes or edges. We formalize this task by defining the Markov Chain Monitoring problem.Given an initial distribution of items over the nodes of a Markov chain, we wish to estimate the distribution of items at subsequent times. We do this by asking a limited number of queries that retrieve, for example, how many items transitioned to a specific node or over a specific edge at a particular time. We consider different types of queries, each defining a different variant of the Markov Chain Monitoring. For each variant, we design efficient algorithms for choosing the queries that make our estimates as accurate as possible. In our experiments with synthetic and real datasets, we demonstrate the efficiency and the efficacy of our algorithms in a variety of settings.

AB - In networking applications, one often wishes to obtain estimates about the number of objects at different parts of the network (e.g., the number of cars at an intersection of a road network or the number of packets expected to reach a node in a computer network) by monitoring the traffic in a small number of network nodes or edges. We formalize this task by defining the Markov Chain Monitoring problem.Given an initial distribution of items over the nodes of a Markov chain, we wish to estimate the distribution of items at subsequent times. We do this by asking a limited number of queries that retrieve, for example, how many items transitioned to a specific node or over a specific edge at a particular time. We consider different types of queries, each defining a different variant of the Markov Chain Monitoring. For each variant, we design efficient algorithms for choosing the queries that make our estimates as accurate as possible. In our experiments with synthetic and real datasets, we demonstrate the efficiency and the efficacy of our algorithms in a variety of settings.

KW - 113 Computer and information sciences

U2 - 10.1137/1.9781611975321

DO - 10.1137/1.9781611975321

M3 - Conference contribution

SP - 441

EP - 449

BT - Proceedings of the 2018 SIAM International Conference on Data Mining

A2 - Ester, Martin

A2 - Pedreschi, Dino

PB - Society for Industrial and Applied Mathematics

ER -

Chaudhari HA, Mathioudakis M, Terzi E. Markov Chain Monitoring. julkaisussa Ester M, Pedreschi D, toimittajat, Proceedings of the 2018 SIAM International Conference on Data Mining. Society for Industrial and Applied Mathematics. 2018. s. 441-449 https://doi.org/10.1137/1.9781611975321