I wonder if there's any development of this, since this paper is from 2016.
This is an example of an NP-hard problem that surprisingly broadly applies to everyday situations, just like the bin-packing problem that has been on the front page recently. Do you know of other NP hard problems with surprising applicability to everyday situations?
I'm one of the authors of the paper, nice to see it on HN.
I remember when we first experimented with this, the compression improvement compared to our previous heuristic was massive, but the algorithm took a day to run on a double-digit-node Giraph cluster for a single index shard. I was very skeptical we'd ever be able to use it in production, given that we had to run it on thousands of index shards every few days.
Eventually we reimplemented it in C++, optimized all the data structures to make them fit in memory, and we were able to run it in a couple of hours on a single (beefy) machine. Over the years it has been optimized further.
The algorithm has been reproduced externally with an open-source implementation [1], which AFAIR was pretty good when I looked at it.
I actually think this is a great reminder to how much things can be optimized. Especially if we are talking about research code. All too often I see people point to python code and talk about it being slow as if someone couldn't rewrite it in C for massive improvements. llama.cpp is a great example of this and there's lots of similarly low hanging fruit in ML
This is such a nice and straightforward result. Encode the vertex ID's using locality-preserving integers, and then store the deltas between the ID's instead of the ID's themselves.
7 comments
[ 3.1 ms ] story [ 31.1 ms ] threadThis is an example of an NP-hard problem that surprisingly broadly applies to everyday situations, just like the bin-packing problem that has been on the front page recently. Do you know of other NP hard problems with surprising applicability to everyday situations?
One that I find very interesting is optimizing function layout in binaries to improve their compressibility [2], which is important for mobile apps.
[1] https://scholar.google.com/scholar?cites=1196492606453931313...
[2] https://arxiv.org/pdf/2211.09285
We worked on improvements to this following our reproducibility study including a synchronized iterative version and alternative estimation functions.
You can find the paper here if you're still interested!
https://jmmackenzie.io/publication/tkde22/
I remember when we first experimented with this, the compression improvement compared to our previous heuristic was massive, but the algorithm took a day to run on a double-digit-node Giraph cluster for a single index shard. I was very skeptical we'd ever be able to use it in production, given that we had to run it on thousands of index shards every few days.
Eventually we reimplemented it in C++, optimized all the data structures to make them fit in memory, and we were able to run it in a couple of hours on a single (beefy) machine. Over the years it has been optimized further.
The algorithm has been reproduced externally with an open-source implementation [1], which AFAIR was pretty good when I looked at it.
[1] https://culpepper.io/publications/mm+19-ecir.pdf