Title:	Trees for robust summaries in small sliding windows.
Author:	Richard A. O'Keefe (ok@cs.otago.ac.nz)
Outline:

    Computing statistical summaries is easy when all the data are available
    in your computer's memory.  When summaries are to be based on a "window"
    on the data that moves through time, we have the sliding window model.
    Much current work is concerned with the large sliding window model,
    where even the window is too big to fit in memory.

    The small sliding window problem is where summaries are to be computed
    based on a sliding window and the window can fit in memory but either
    the complete data set does not fit into memory or it is not yet available
    when the summaries are needed.

    The application that inspired this study has several hundred measurements
    measured every millisecond over a period of hours, where summaries based
    on several minutes of data could be useful in spotting problems as they
    occur; on today's machines a small sliding window.

    Data structures for special cases, such as H\"ardle and Steiger's
    AS 296 for running medians, are known.  It turns out that a single
    data structure can handle any or all of

	plain, trimmed, and Winsorized means;
	plain, trimmed, and Winsorized standard deviations;
	medians, interquartile range, range, or any fixed quantile

    in O(log W) time per sample, where W is the size of the window,
    and can handle

        median absolute deviation

    in O((log W)^2) time per sample -- I hope to reduce this to O(log W).