Investigate Forward Decay paper for possible data structures

[sritchie]

The paper: http://dimacs.rutgers.edu/~graham/pubs/papers/fwddecay.pdf

The tantalizing abstract:

While exponential time decay is commonly used in practice, other decay functions (e.g. polynomial decay) are not, even though they have been identified as useful. We argue that this is because the usual definitions of time decay are “backwards”: the decayed weight of a tuple is based on its age, measured backward from the current time. Since this age is constantly changing, such decay is too complex and unwieldy for scalable implementation.

In this paper, we propose a new class of “forward” decay functions based on measuring forward from a fixed point in time. We show that this model captures the more practical models already known, such as exponential decay and landmark windows, but also includes a wide class of other types of time decay. We provide efficient algorithms to compute a variety of aggregates and draw samples under forward decay, and show that these are easy to implement scalably. Further, we provide empirical evidence that these can be executed in a production data stream management system with little or no overhead compared to the undecayed computations. Our implementation required no extensions to the query language or the DSMS, demonstrating that forward decay represents a practical model of time decay for systems that deal with time-based data.

• Coda Hale discusses the algorithm in this presentation
• And it's used in metrics: http://metrics.dropwizard.io/3.1.0/apidocs/com/codahale/metrics/ExponentiallyDecayingReservoir.html
• Go implementation link: https://github.com/samuel/go-metrics/blob/master/metrics/edsample.go#L94

[e-hat]

This is kind of old but it sounds like a fun project. What would the deliverable for this "investigation" be, exactly? I'd love to check it out.