License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.ICCSW.2012.29
URN: urn:nbn:de:0030-drops-37613
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2012/3761/
Go to the corresponding OASIcs Volume Portal

Chis, Tiberiu S. ; Harrison, Peter G.

Incremental HMM with an improved Baum-Welch Algorithm

pdf-format:
6.pdf (0.5 MB)

Abstract

There is an increasing demand for systems which handle higher density, additional loads as seen in storage workload modelling, where workloads can be characterized on-line. This paper aims to find a workload model which processes incoming data and then updates its parameters "on-the-fly." Essentially, this will be an incremental hidden Markov model (IncHMM) with an improved Baum-Welch algorithm. Thus, the benefit will be obtaining a parsimonious model which updates its encoded information whenever more real time workload data becomes available. To achieve this model, two new approximations of the Baum-Welch algorithm are defined, followed by training our model using discrete time series. This time series is transformed from a large network trace made up of I/O commands, into a partitioned binned trace, and then filtered through a K-means clustering algorithm to obtain an observation trace. The IncHMM, together with the observation trace, produces the required parameters to form a discrete Markov arrival process (MAP). Finally, we generate our own data trace (using the IncHMM parameters and a random distribution) and statistically compare it to the raw I/O trace, thus validating our model.

BibTeX - Entry

@InProceedings{chis_et_al:OASIcs:2012:3761,
  author =	{Tiberiu S. Chis and Peter G. Harrison},
  title =	{{Incremental HMM with an improved Baum-Welch Algorithm}},
  booktitle =	{2012 Imperial College Computing Student Workshop},
  pages =	{29--34},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-48-4},
  ISSN =	{2190-6807},
  year =	{2012},
  volume =	{28},
  editor =	{Andrew V. Jones},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2012/3761},
  URN =		{urn:nbn:de:0030-drops-37613},
  doi =		{10.4230/OASIcs.ICCSW.2012.29},
  annote =	{Keywords: hidden Markov model, Baum-Welch algorithm, Backward algorithm, discrete Markov arrival process, incremental workload model}
}

Keywords: hidden Markov model, Baum-Welch algorithm, Backward algorithm, discrete Markov arrival process, incremental workload model
Collection: 2012 Imperial College Computing Student Workshop
Issue Date: 2012
Date of publication: 09.11.2012

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI