How to best maintain a database of average time-related values?

I want to store the average values of some data that is occasionally generated by users, which I then use in my application to predict future data. Now the problem I have is that this data may grossly change during the day - so for example users coming in at night time may generate much lower values then users coming in during the morning, so just keeping a simple average will not give me a reasonable prediction accuracy.

Some I need to store some kind of time based average - for example a naive solution would be to store the average value for each hour of the day - so I keep 24 averages, one for all the users that generated data between 12AM and 1AM, the second for all the users that generated data between 1AM and 2AM, and so forth.

I only have a few of issues with this approach: 1. to predict data properly I'd still need to consult a few values (lets say, 2 hours ahead and 2 hours back from now) which I may not have the resources to do. I rather consult a single value if it doesn't hurt my accuracy too much. 2. I also want to have this data remembered only for recent times - if very low values where generated a couple of years ago but since last month everyone is generating high values, then for me to predict data for the near future I need to be able to respond better then what an average of all the data ever created can give me. For the sake of the argument lets say that everything older then 90 days is not really relevant. 3. The reason that I want to use an average value and not just keep all the data ever generated by the users is that I expect a lot of data - I need to store such data for each of 100K to maybe 10M data points, for millions of weekly data entries from users - at the least. I also might want to split the data even further for each data point - maybe based on some user classification.

I'd appreciate it if anyone can give me some hints on how to best calculate my average data without required a huge data storage facility :-)

[hint - yes, its for a GIS application ]


ANSWERS:


It sounds like there are two important bits of information in your data set. How many days old the data is, and what hour of the day that it is.

The predicted value for a future time could be calculated as a weighted average over the data set, with weights decreasing with age, and decreasing also with how far off the hour for the predicted value it is.

Edit : if the most important thing is not hanging onto data :

Setting up bins as you propose (the naive solution) seems like the most reasonable approach. As new data comes in and is 'averaged' with the binned data, the new data can be given a larger weight to help recent changes overcome the 'inertia' of all the historical data.


Use a view to calculate your expected values. That way, you get dynamic construction of your means, and it's simple to query.


Have you looked at the formulas on calculating moving averages? There's a number of methods defined on wikipedia.


I think a round robin database (e.g., rrdtool) would be ideally suited for your purposes. Whatever your favorite language is, there is certainly a programming API.

Best regards, Noah


Why not just store all the user generated values, and then calculate exactly what you want when you want it? You can always set up an archiving script to clear out old data when you don't need it any more.

In this way you don't introduce inaccuracies by doing calculations with calculated values.



 MORE:


 ? Algorithm for merging two max heaps?
 ? bellman ford algorithm trace
 ? bellman ford algorithm trace
 ? bellman ford algorithm trace
 ? Bellman-ford algorithm for one vertex
 ? Finding all shortest paths from source to all vertices in a digraph
 ? Finding all shortest paths from source to all vertices in a digraph
 ? Finding all shortest paths from source to all vertices in a digraph
 ? Find a monotonic shortest path in a graph in O(E logV)
 ? Find the lowest-cost shortest path from one node to another?