1
$\begingroup$

I have a value that increases by unknown increments at unknown times. Given a time, I need to check how much it has increased between that time and now.

I could simply store every time/increase pair whenever the value is increased, but this would be too much data to reasonably store.

For example:

DATA:
Value = 0 @ 0:00
Value = 2 @ 0:04
Value = 7 @ 0:05
Value = 52 @ 0:07 (Current time)

RESULT:
1 Second: 52
3 Seconds:  2 + 7 + 52 = 61

I am not sure what I am trying to do is even possible. But, is there a way I can store the increments such that I can keep the file size reasonably small, and still find a decent approximation of the increase in the value? It does not need to be exact - a margin of error less than 5% would be acceptable.

Improve this question
$\endgroup$
4
  • $\begingroup$ Note that the sequence of increments could be, essentially, any sequence of (nonnegative) numbers. Storing the increments, rather than the actual value, not only makes your queries hard to answer (you have to sum up a range of the increments) but also doesn't make the data any more compressible. $\endgroup$ – David Richerby Sep 6 '17 at 17:03
  • $\begingroup$ Your margin of error, as formulated, doesn't save you too much. Take any update, taking place at time $t$. You need to be able to answer what the increase is during the interval $[t-\epsilon,t+\epsilon]$ at an accuracy of 5%. So you have to record that some update occurred at time $t$, though you can quantize it to save some space. $\endgroup$ – Yuval Filmus Sep 6 '17 at 19:17
  • 1
    $\begingroup$ @DavidRicherby Recording the increments (or changes) would result in smaller numbers, which can be compressed more easily. Any extreme case is a 16 bit sound recording at 44.1KHz, where each sample is in the range +/- 32767, but changes from sample to sample will usually be much smaller. So recording say the first sample every second, then Huffman coding the change from sample to sample gives you a not completely useless lossless compression. Finding an individual sample takes long, but you are interested in consecutive samples so that's no big problem. $\endgroup$ – gnasher729 Feb 18 '18 at 12:41
  • $\begingroup$ @gnasher729 The increments are only smaller numbers if the samples are correlated. Probably in most situations, they will be, but the question doesn’t say they are. $\endgroup$ – David Richerby Feb 18 '18 at 12:44
1
$\begingroup$

In the case of storage and querying from the storage i.e. if you can first get all time:value pairs, you can use curve fitting (regression) to get the polynomial function v=f(t), where v = value and t = time which will not be accurate, may even be outside 5% error margin; but would the get the work done in a very low file size and acceptable(?) margin of error.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.