by Mr_P on 5/1/2021, 2:30:28 AM
by londons_explore on 4/30/2021, 10:54:02 PM
Isn't this the idea behind MIPMAPS in computer graphics?
In the tracing world, I believe the opensource pulseview/sigrok does this. It makes the UI very responsive even with gigabytes of data. I just wish it also integrated data compression of some kind so I could fit more trace than I have RAM (it can't be all that hard to intelligently compress a super repetitive signal in a way which still allows this fast zooming and scrolling - replacing some tree nodes with LZ77 style backreferences ought to do the trick)
by quotemstr on 4/30/2021, 10:46:24 PM
I don't like it when programs rely on VM overcommit in such a way that they break on other systems. Even if you don't care about Windows (which is a strict accounting no-overcommit system), you should care about Linux, which can be configured to do strict accounting the way Windows does.
If you want to use the big address-space carve-out trick, you can, but the right way to do it is to PROT_NONE the parts of the address space you aren't using and install a signal handler to commit bits of your carveout as they're used.
by contravariant on 4/30/2021, 11:49:05 PM
Not sure how they got the 3N space overhead for Fenwick trees. If you do it right then Fenwick trees won't have any space overhead (in fact the conversion from an array to a Fenwick tree can be done in place). Though I suppose they might suffer from catastrophic cancellation if you're not careful.
by rokob on 4/30/2021, 11:36:54 PM
I had some time series data which was append only like this. I started looking into skip lists and realized I might as well make it deterministic where the height of a node is basically popcnt. It ended up looking and behaving a lot like this.
by lambda_obrien on 5/1/2021, 5:21:26 AM
Check out http://btrdb.io/ which is a similar idea. It's a distributed database as well. It was designed for storing billions or even trillions of records for electrical data from hundreds of sources at once.
It was written by a couple of friends of mine and others, so I'm not sure how it compares to the article link, as I'm not a databases expert.
If generalized to 2D (and over the unit sphere), you'd get Google's S2 library (https://s2geometry.io/).
In 3D, the same can be done with morton codes (or a 3D hilbert curve) to build an implicit octree. Some raytracing systems use this for fast BVH construction.
In either case, this approach differs from mipmaps in that the underlying data can be sparse, and is simply stored in a sorted array.