3 ms·

This seems fascinating, but how much is that bullshit? E.g the claimed performance numbers... Or many of the use cases... Indeed, many Heuristics are based on

This seems fascinating, but how much is that bullshit? E.g the claimed performance numbers... Or many of the use cases... Indeed, many Heuristics are based on a prioris and would benefits from plasticity/dynamicity à la PGO and from classic use of statistics to drive program optimizations decisions. I have big doubts that a neural network would be better but I would love to be proved wrong, this could be big. It's from 1.5 years ago though. Edit: this is the paper for replacing some major data structures with a neural network that take into input the key and output the position in memory. One big downside is that is has a margin of error which is very often unacceptable. And I guess it would mostly work for static size (which are already O(1) structures not growables ones (otherwise it should be trained again? Baidu introduced continual learning with ernie 2 but the overhead must be so huge..)

ModernMech 7y ago
I could see something like this being used to pick parameters like the adjusting the size of a hash table based on the data it's holding in order to optimize memory consumption, or adjusting the degree of a B-tree. That might yield some great results. But the suggestion here is to that anyplace we use heuristics we instead use neural nets, including places like schedulers. But using heuristics doesn't mean it's free of guarantees or provable properties. When you start replacing things like a scheduler with neural networks I start getting nervous. Are you telling me that maybe my memory could get into some weird layout that happens to be a false positive in my scheduler algorithm that causes all kinds of mayhem with my system? I don't think I want to sign up for that.
ndr 7y ago
> One big downside is that is has a margin of error which is very often unacceptable. You should look at the paper they mention The Case for Learned Index Structures[0]. It covers B-Tree-Index and how to use Hybrid Indexes to bound the errors so that "bad" answers from the model perform no worse than the standard data structure. For a lighter read this paper was also covered by Adrian Colyer in an issue of the morning paper[1]. [0] https://arxiv.org/abs/1712.01208 https://arxiv.org/abs/1712.01208 [1] https://blog.acolyer.org/2018/01/08/the-case-for-learned-index-structures-part-i/ https://blog.acolyer.org/2018/01/08/the-case-for-learned-ind... [edit: formatting]
- The_rationalist 7y ago
  Yes, thank you! I actually wanted to include it in my comment but brainfarted and forgot to paste the link ><'.
- stochastic_monk 7y ago
  I don’t buy their case. A good hash table outperforms it in speed and memory [0]. [0] https://dawn.cs.stanford.edu/2018/01/11/index-baselines/ https://dawn.cs.stanford.edu/2018/01/11/index-baselines/

ModernMech 7y ago

I could see something like this being used to pick parameters like the adjusting the size of a hash table based on the data it's holding in order to optimize memory consumption, or adjusting the degree of a B-tree. That might yield some great results. But the suggestion here is to that anyplace we use heuristics we instead use neural nets, including places like schedulers. But using heuristics doesn't mean it's free of guarantees or provable properties. When you start replacing things like a scheduler with neural networks I start getting nervous. Are you telling me that maybe my memory could get into some weird layout that happens to be a false positive in my scheduler algorithm that causes all kinds of mayhem with my system? I don't think I want to sign up for that.

ndr 7y ago

> One big downside is that is has a margin of error which is very often unacceptable. You should look at the paper they mention The Case for Learned Index Structures[0]. It covers B-Tree-Index and how to use Hybrid Indexes to bound the errors so that "bad" answers from the model perform no worse than the standard data structure. For a lighter read this paper was also covered by Adrian Colyer in an issue of the morning paper[1]. [0] https://arxiv.org/abs/1712.01208 https://arxiv.org/abs/1712.01208 [1] https://blog.acolyer.org/2018/01/08/the-case-for-learned-index-structures-part-i/ https://blog.acolyer.org/2018/01/08/the-case-for-learned-ind... [edit: formatting]

The_rationalist 7y ago
Yes, thank you! I actually wanted to include it in my comment but brainfarted and forgot to paste the link ><'.
stochastic_monk 7y ago
I don’t buy their case. A good hash table outperforms it in speed and memory [0]. [0] https://dawn.cs.stanford.edu/2018/01/11/index-baselines/ https://dawn.cs.stanford.edu/2018/01/11/index-baselines/