Code

There are two popular variants of the Holt-Winters forecasting method; RRDtool
authoroetiker <oetiker@a5681a0c-68f1-0310-ab6d-d61299d08faa>
Fri, 15 Jun 2007 07:59:01 +0000 (07:59 +0000)
committeroetiker <oetiker@a5681a0c-68f1-0310-ab6d-d61299d08faa>
Fri, 15 Jun 2007 07:59:01 +0000 (07:59 +0000)
commit51fcea2cbf9721f012f2f0d43c604a3aaf684ee8
tree081e0c7c89d47c65c7f91e8e9dd72fe35b54cb41
parent5493345a7b1e79ef80e6f333b3b5162b976390b9
There are two popular variants of the Holt-Winters forecasting method; RRDtool
supports the "additive" method, which means that seasonal variation is simply
added to the baseline. For our application, it would be more appropriate to use
the "multiplicative" Holt-Winters method, where seasonal variation is a
coefficient multiplied by the baseline.  Quick example to illustrate the
difference: if the average doubles season-over-season, the additive method
would predict the delta between min and max to be constant, whereas the
multiplicative method would predict the delta to double as well.

Attached is a patch against trunk to support the multiplicative method.  I've
done this with a new consolidation function, MHWPREDICT, which is essentially
interchangeable with HWPREDICT. There is a noticeable improvement in prediction
deviations for certain types of functions; the attachments show HWPREDICT and
MHWPREDICT predictions for a function with an x*sin(x) component.

Because HWPREDICT and MHWPREDICT differ only in their equations, I've factored
out their math into rrd_hw_math.c. The appropriate smoothing functions are
passed to the update functions in a container of function pointers, which are
called where appropriate. Thus the additive and multiplicative methods use the
same update functions, and the right equations are evaluated without having
flag checks everywhere. This approach, I think, makes the algorithms quite
clear, with minimal duplicate code.

I have moved update_hwpredict, update_seasonal, update_devpredict,
update_devseasonal, and update_failures into a separate file, rrd_hw_update.c,
with some slight refactoring related to rrd_hw_math.c. I ran some
regression tests against trunk to make sure I didn't break anything with
the existing HWPREDICT code.

MHWPREDICT uses the same deviation smoothing and failure detection algorithms
as HWPREDICT.

Some helpful references on the multiplicative Holt-Winters method:

http://www.it.iitb.ac.in/~praj/acads/seminar/04329008_ExponentialSmoothing.pdf
(a student's quick overview of additive vs. multiplicative HW)

http://ideas.repec.org/p/msh/ebswps/1999-1.html (paper on variations to the
multiplicative Holt-Winters, including variance calculations; FYI, my
implementation uses "Model 1")

My employer and the owner of this patch (IMVU, Inc.) is happy to license it
under the same terms as RRDtool, i.e. give it to the project.
-- Evan Miller emiller imvu.com

git-svn-id: svn://svn.oetiker.ch/rrdtool/trunk/program@1125 a5681a0c-68f1-0310-ab6d-d61299d08faa
17 files changed:
doc/rrdcreate.pod
doc/rrdtune.pod
src/Makefile.am
src/rrd_create.c
src/rrd_dump.c
src/rrd_format.c
src/rrd_format.h
src/rrd_graph.c
src/rrd_hw.c
src/rrd_hw_math.c [new file with mode: 0644]
src/rrd_hw_math.h [new file with mode: 0644]
src/rrd_hw_update.c [new file with mode: 0644]
src/rrd_hw_update.h [new file with mode: 0644]
src/rrd_info.c
src/rrd_restore.c
src/rrd_tune.c
src/rrd_update.c