4

At work I'm dealing with a situation where we have a large amount of time series data and need to display sections of it to the user at a time. The data essentially has an infinite number of records, and so it's not possible for the client to load the entire dataset at once. However, the API call to request sections of data is slow/expensive, so I want to cache already-loaded data clientside and not have to re-request it.

An analogy would be when you watch a video online and skip forwards and backwards. The player downloads fragments of the video based on what the user is currently trying to watch and stores them in case the user watches that segment again.

There are a few differences between my use case and the video example though:

  • My data set is sparse. There may be regions of several weeks with no data points in them. I need to differentiate between "no data" and "not loaded".

  • My data set doesn't have discrete segments. In an HLS or DASH video the stream is split into segments (usually 10 seconds long) which provide discrete intervals where the loading should take place. My data can be loaded between any two points in time, and as the user can zoom in or out of the data the distance between these points may not even be the same.

  • My data set is unbounded. In a video, there's a clear start and end to the video. In my data set, you can go forwards and backwards theoretically infinitely. (Although in practice the length is limited by what dates can be stored in our backend, it's still a very large amount of time)

I'm self taught in programming and I don't know the name of this concept, but I feel there must be one. I'm capable of implementing what I need myself, but I'm hoping to avoid reinventing the wheel.

  • 3
    I don't think it's worth me going to an answer for this, but you may want to look into the concepts of Lazy Loading, Paging, and the Flyweight Pattern (depending on how much state is shared between points) – e_i_pi Jan 11 '18 at 2:13
1

If it were not for the lack of discrete sections I would think of this as a page caching/replacement algorithm. Just because your user selects an arbitrary range doesn't necessarily mean you cannot still retrieve the set of pages that contain that range right? Do the rows of your data set have an auto-incrementing id? if so then you can easily partition your data into pages consisting of a fixed number of records. For retrieval of the pages containing your data you can simply use modular arithmetic, i.e look up the id then do (id mod n) where n is page size to get first record of containing page, and do (id mod n) + n for the page at the end of the range. If your data doesnt have this, then potentially you can generate the numbers historically, and generate them automatically from now onwards?

https://en.wikipedia.org/wiki/Page_replacement_algorithm

Id also consider using some kind of library. Not sure of your language but a quick search shows up this interesting project which you could use for reference :

https://github.com/vpetrigo/caches

  • Good suggestion. Sadly any auto-incrementing IDs in the data are not in chronological order, and due to the nature of the data it's not feasible to create any ordered numeric identifier. I could potentially partition the data into pages, but I couldn't do so in a way that has a consistent number of records per page. – Joshua Walsh Jan 11 '18 at 0:02
  • My language is JavaScript, but I'd be happy to see an implementation in any language. – Joshua Walsh Jan 11 '18 at 0:03
  • 1
    I guess what is important is this : (a) given a record, can you identify the page that contains it, and (b) given a page can you immediately know the lower and upper bound of the records in the page. – the4thamigo_uk Jan 11 '18 at 0:04
  • I could potentially make one day a "page". In that case given the day I can get all the items on that page, and given an item I can know what page it belongs to. – Joshua Walsh Jan 11 '18 at 0:05
  • 1
    tbh I like the idea of writing some kind of page caching library myself! – the4thamigo_uk Jan 11 '18 at 0:13
-1

Not sure if this is what you are already considering: but on reflection, given your use case, you can probably gain an lot of benefit from a very simple caching algorithm, whereby you maintain a single variable length segment in the cache. When you exceed the bounds left or right, you simply grow the segment by the required amount (preferably several times the required amount to avoid further queries). Similarly if you zoom out you expand both ends of the segment. Zooming in, obviously does not require the segment to change. You would probably need to limit the maximum size of the segment, at which point if you move left then you lose a corresponding section from the right end and vice-versa. Moving to an entirely different segment should retain the data from the intersection with the old segment, and discard the data outside the new segment. For this implementation you probably need an efficiently implemented double ended list (https://github.com/petkaantonov/deque).

One use case in which this doesnt work well is when the user switches between two disjoint segments that are more than the size of the maximum segment size, or if they jump around several remotely located regions of data.

Unfortunately, I dont know the same for such an algorithm...

One other thought to bear in mind is to be 100% sure where the bottleneck is. Are you confident it isnt the datatable or query that is poorly optimized (e.g. indexes). It could be that the database is poorly resourced, or the speed of marshalling the large amount of data, or it could be the way the data is loaded into javascript objects is inefficient, or other things like latency of the network round-trip.

  • wonder what's the point of posting second answer instead of editing prior one – gnat Jan 11 '18 at 9:23
  • This is actually very similar to the functionality we already have implemented. Unfortunately, due to the speed of the data source it's very slow if we discard cached data, and the memory requirements of storing all the data in a contiguous range are challenging to work with. I've done quite a bit of analysis using Firefox's Flame Chart tool and I'm confident I know where the bottlenecks lie. This isn't actually our main bottleneck, (it's maybe our 3rd biggest) but given that we're doing a rewrite anyway I want to fix it. – Joshua Walsh Jan 11 '18 at 11:29

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.