2 ms·
Just to give you an idea of how effective this strategy seems to be, this seems very similar to what the COST in the land of databases submission the other day
by kbenson 9y ago
Just to give you an idea of how effective this strategy seems to be, this seems very similar to what the COST in the land of databases submission the other day was talking about, where choosing interesting, fitting algorithms for the problem instead of large distributed but general systems often yields very good results (enough such that a single thread can often beat 100+ core distributed systems).
In one of the linked prior blog posts[2] of his he linked to in the beginning of that article, he said this:
Using the Hilbert curve layout leads to a very simple compressed representation: having sorted the u64 values it uses to represent edges, one can simply delta-encode them (writing the differences between adjacent values). Because the Hilbert curve teases out locality, the gaps are often quite small, and therefore compress nicely. When I combined a variable-length integer encoding with gzip, the resulting file was only 45GB; about 2.8 bits per edge). Decompressed (with just the variable-length delta encoding), it is 154GB, which is the representation I used to get the measurements above.
He then goes on in his posts to comically trounce some large distributed systems.
1: https://news.ycombinator.com/item?id=15332051 https://news.ycombinator.com/item?id=15332051
2: https://github.com/frankmcsherry/blog/blob/master/posts/2015-02-04.md https://github.com/frankmcsherry/blog/blob/master/posts/2015...
- frankmcsherry 9y ago!#$!@# I was going to go try that out. ;) When doing the Chaos/Order stuff, the decompression was about half the CPU cycles, so thinning that could help. Fwiw, the encoding I used wasn't VByte; because I was doing strict increments, I knew `0` wasn't a valid value to see, and used it to encode variable byte lengths (number of zeros: number of valid data bytes). Not smart, but easy to hack up, and gave me back 128-255 in one byte. I'm curious to check this out, now!