I haven't read that paper (Learned Index Structures), but things like gperf have existed for decades. Are these enhanced data structures dynamic, i.e. unlike gperf which is a static one, does it reoptimize as you insert new elements?
In the case of the hash table, I assume it's using the model to compute the hash function.
No, it doesn't handle inserts. On the other hand, the paper writes:
"An ... approach to handling inserts is to build a delta-index. All inserts are kept in buffer and from time to time merged with a potential retraining of the model."
Under some assumptions it does handle inserts. From [1]:
Finally, assume that the inserts follow roughly a similar pattern as the learned CDF; [...] Under these assumptions the model might not need to be retrained at all.
I thought it was a stretch when reading that medium post. Now reading this and thinking about it after finishing two undergraduate classes one on operating systems and another on compilers, the machine learning for systems part makes a lot of sense, apart from the heuristics the learned index structures idea is just fascinating.
Another illuminating sentence from the paper was this:
>This leads to an interesting observation: a model which predicts the position given a key inside a sorted array effectively approximates the cumulative distribution function (CDF). We can model the CDF of the data to predict the position as: p = F(Key) ∗ N
Maybe it's just my very limited knowledge as an undergrad but I'm feeling that this can be the start of something big. Another idea that just came to me after is how much of this ML is applicable to the domain of cryptography. In my security class it seemed like much of the famous hash functions for example were somehow "found" in vast space of potential schemes.
Yeah, it is funny that ML, which is biggest fears driven by the media as the ultimate job destroyers, would put this generation of programmers in danger as well.
However, the paradigm shift is inevitable, once discovered, people will use it, and use it anywhere possible.
In the case of the hash table, I assume it's using the model to compute the hash function.