Is there a name for a data structure/concept where certain regions of a data set are loaded?

Question

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.

Answer 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

Answer 2

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.