CODEWITHSUNDEEP
c#wpfalgorithmdata-structuresvisiblox
user3096803
user3096803

Reputation:

Data Structure/Algorithm that handles Expired Data

I am plotting N series of data. Each series contains N data points that have a time of occurrence in UNIX time with a precision of 5 decimal places. The data points may have indifferent intervals, thus it is very unlikely that two or more data points will share the same time of occurrence.

I am storing all of the data points in one sorted collection. Smaller series that are plotted are constructed from this data set. The problem is that if I animate the data along a timeline, one series may not have any recent points, so the points cannot stay in the viewed collection as they are obviously not in the same location. For example, one data series may stop having points, and then start again much later. Here are arrays of data points(their UNIX time of occurrence).

allpoints = { 120.5, 130.5, 135.5, 140.5, 140.5, 145.5, 150.3, 150.5, 160.5, 170.5, 180.5, 190.5, 200.5, 200.5 };

series1 = {135.5, 140.5, 145.5, 150.5, 200.5};

series2 = { 120.5, 130.5, 140.5, 150.3, 160.5, 170.5, 180.5, 190.5, 200.5 };

Surely I can't keep all of the old points from series1 going forward, as it essentially doesn't exist for 50 seconds while the points from series 2 are still being plotted.

What's the best way for me to keep the data in these series up to date without having to check every point every time another point is added from the main data points collection? Maybe a priority queue or something?

Thanks

Upvotes: 0

Views: 161

Answers (1)

Mazvél
Mazvél

Reputation: 1009

If I understand correctly, your problem is that once you get a new point from the main dataset you only want to add it to existing series IF the time interval is not bigger than some constant, the interval to the last point in the respective series.

So your question is essentially, when can you delete older points from the series, and how to do so efficiently.

What you could use is a list, where you can keep track of the tail and the head. Then once you get a new datapoint you calculate the time for oldest points you want to keep. Then you loop through every list and delete the points with timestamp prior to the calculated time. So your algorithm is as follows:

  1. New point P comes.
  2. Add P to the head of it's respective series.
  3. Calculate time T based on P.time and MAX_INTERVAL. (T = P.time - MAX_INTERVAL)
  4. For every active series: Loop from tail to head. (Let's call the current point you are looking at tempPoint).
  5. IF tempPoint.time < T: DELETE and Go to tmpPoint.next. ELSE go to next series. (Special care needs to be taken when you reach the head node, because then you will need to delete the series from the list of series).

You could also start with checking the head of the series just in case you could delete that whole series, but it depends on the nature of your data and how frequently you expect points in each series.

I hope this answers your question.

Upvotes: 0

Related Questions