title: Data structure for updating values and querying the state of values at a time in the past
body: <p>Suppose you're interested in a bunch of independent time-varying values, each of which represents the current state of something. The values don't change on any fixed schedule and new values can't be predicted from old ones. For the sake of a concrete example, let's say you have a bunch of stocks and you're interested in keeping track of their values, and you get an update about an individual stock whenever a trade is made on that stock. (My actual problem isn't about stocks, but hopefully they make what I'm getting at more understandable.)</p>
  
  <p>In addition to just knowing the current price of each stock, you'd also like to be able to pick an arbitrary point in the past and get a "snapshot" that told you what the most recent trading price for each stock was at that time. So for instance, you should be able to say "What was the most recent value of every stock I'm tracking as of 4:53PM last Tuesday?" and get a precise answer efficiently.</p>
  
  <p>I can think of three ways to do this, but I'm not very happy with any of them.</p>
  
  <p><strong>1. Keep a journal.</strong> Maintain a list of all trades in time-sequence order. Update is just adding to the list, and query is a linear scan backwards in time starting with the first entry whose timestamp is on or earlier than the specified time stamp. This would make update a constant time operation, but you might potentially have to scan the entire journal to find a value for all trades, so Update is O(1) and Snapshot is O(u) where u is the total number of updates. Memory required is O(u) for obvious reasons.</p>
  
  <p><strong>2. Write checkpoints.</strong>
  Maintain a single journal as before, but instead of each entry containing just new stock price, the update contains the current price (as of that update) for <em>every</em> stock. This is cheap to calculate: since the last update has all that information too, you just copy it all over except for the one stock whose price actually changed. Now Snapshot can be done with an O(log u) operation (using binary search on the journal to locate the last entry that comes before or on the specified timestamp). However Update becomes O(s) where s is the number of stocks in the system, and furthermore the total memory required goes from O(u) in the first strategy to O(s*u) --- both of which are problems if both s and u are large.</p>
  
  <p><strong>3. Separated journals.</strong>
  Maintain a separate journal for each stock, and write updates for each stock into its own journal, again in chronological order. To snapshot, go over each journal and use a binary search to find the correct update. It requires O(u) memory, Update is an O(1) operation, and Snapshot can be done in O(s * log u) time. This is my favorite method of the three, but I feel like it could probably be improved upon, since it ignores any relationship between the timing of updates across different stocks. </p>
  
  <p>Is there a better way I'm missing? Is this a problem that has been studied and has a generally-accepted solution?</p>