The Case for Learned Index Structures

I highly recommend people give this paper a read. I think it points the way to a radical redesign of fundamental parts of the system stack over the next 5-10 years. If you work in systems and you aren’t thinking about this stuff, you’re about to be lapped. The Case for Learned Index Structures: https://arxiv.org/pdf/1712.01208v1.pdf

> OTOH the standard library sort can be improved if you know the distribution of the numbers you're sorting (e.g., small numbers can bucket sort, small lists can use a sorting network, etc). If this thing can efficiently almost-correctly-sort because it's better at these types of pattern matching, we can just run a final pass of insertion sort to make it useful! I haven't read this paper, but that strategy was exactly the strategy behind "The Case for Learned Index Structures"[0]. The idea was you could train a model to predict the location of a row based on a primary key. After computing the model, you could then go through every row and compute a bound on how far off the model is from the actual row. To perform a lookup, you start off at the model's guess, then look around based on the bound on the model for a row with the given primary key. [0] https://arxiv.org/abs/1712.01208

> 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 [1] https://blog.acolyer.org/2018/01/08/the-case-for-learned-ind... [edit: formatting]

The LLM is still a "normal algorithm", just one with a fairly large dataset to use. Assigning the algorithm part of LLMs magical properties hinders understanding. The work needed to pick the next output token is very much a classical algorithm. Algorithms can be based on training and/or use data just fine, too. https://arxiv.org/abs/1712.01208 (Now, the weights used, those we kinda really don't understand the same way we understand the processing, and the approach to looking for structures in weights sometimes looks more like archeology or anthropology than computer science.) It sounds like you're trying to express some kind of "but LLMs are so much more" thought. Yes, very much, they are. It's because of the size of the data, there's interesting emergence there. They're still a normal algorithm. (And our brains aren't quite like that; biological things are much more random/chaotic and generally non-reproducible.)

When NPU will become available in most systems, we will see learned indexes like in https://arxiv.org/pdf/1712.01208v1 on client side. If file search indexes and such will be replaced by neural networks, this will be small but measurable improvement in battery life, speed and memory usage.

In theory, you can treat the objects as i.i.d. giving them a uniform prior. In practice, of course only the inputs are inputs and if you were to take that into account then you could avoid collisions, but as you say, you can't really know that ahead of time. Unless you can, such as when there is structure to the inputs or some other source of non-uniformity that you can account for. The topic of learned indexes is worth investigating if you're interested: https://arxiv.org/abs/1712.01208 https://arxiv.org/abs/2012.12501

Also, Learned Indexes Structures: The Case for Learned Index Structures: https://arxiv.org/abs/1712.01208 Learned Indexes for a Google-scale Disk-based Database: https://arxiv.org/abs/2012.12501 And Noms/Dolt Prolly Trees: How to Chunk Your Database into a Merkle Tree: https://dolthub.com/blog/2022-06-27-prolly-chunker/

> we'll see another explosion in practical CPU throughput, combined with a little help from algs and data structures The learned index[1] is basically a variation of this sort of "hint" which relies on getting the right answer most of the time, but from learning the distribution function as a model instead of relying on the programmer to heuristic it. (from that paper) > The key idea is that a model can learn the sort order or structure of lookup keys and use this signal to effectively predict the position or existence of records I haven't seen anything mix this sort of work with an Eytzinger traversal, but there's always diminishing returns for these. [1] - https://arxiv.org/abs/1712.01208

The Case for Learned Index Structures Tim Kraska, Alex Beutel, Ed H. Chi, Jeffrey Dean, Neoklis Polyzotis "Our initial results show, that by using neural nets we are able to outperform cache-optimized B-Trees by up to 70% in speed while saving an order-of-magnitude in memory over several real-world data sets. More importantly though, we believe that the idea of replacing core components of a data management system through learned models has far reaching implications for future systems designs and that this work just provides a glimpse of what might be possible." https://arxiv.org/abs/1712.01208

Could you have someone walk towards the camera with a focus test card and form a map between the sensor and the focus data from the lens itself (FFT, etc)? It would be something analogous to the 'learned indexes' paper. You could then provide any tweening function to give you that focus feeling you need. http://www.vldb.org/pvldb/vol13/p1162-ferragina.pdf https://arxiv.org/abs/1712.01208

Interesting stuff. I thought one of the most interesting papers at NIPS this year was using GPU or TPU for intelligent indexes. https://arxiv.org/abs/1712.01208 Paper is from Jeff Dean and a worth while read, IMO.

This seems like a fairly natural generalization of the idea in "The Case for Learned Index Structures" [1]: speed up some classical algorithm based on heuristics by modeling the data with a neural network that can be tuned to the specific task that the general algorithm is applied to. That said, the O(N) claim is purely sensational. It all depends on being able to determine the distribution parameters with sufficient accuracy in O(N) time, which isn't really guaranteed for all kinds of data you might want to sort. [1] https://arxiv.org/abs/1712.01208

On the one hand, DeepZip does neural net based compression. On the other hand, in "The Case for Learned Index Structures" [1] paper, they replace B-Trees with neural nets: > by using neural nets we are able to outperform cache optimized B-Trees by up to 70% in speed while saving an order of magnitude in memory over several real world data sets Basically ML/DL is coming for the classic data structures, replacing some of them with learning based versions. [1] https://arxiv.org/abs/1712.01208

Google completely gave away K8s including even the brand. So not sure what you think Google will do? They are giving away everything they learned with Borg and you somehow take it as a negative? Really? Do think from a business standpoint not sure why Google would give up the K8s brand but it is good for everyone. I really worry that Google will stop opens sourcing and more important sharing so much through papers when people b*tch so much. Starting to be hard to see why they even do it any longer. Who else have a huge competitive advantage with something like Borg and just gives it away to the industry? But I am someone super curious and just probably spend more time on https://research.google.com/pubs/papers.html Read most of the paper. But then what they presented at NIPS. My favorite paper right now is https://arxiv.org/abs/1712.01208 Bigger example is how much they give away in terms of AI/ML.

Would say Google has a couple gems. DeepMind comes to mind. Also Google Brain has done some pretty interesting things. Probably my favorite of late is from Jeff Dean https://arxiv.org/abs/1712.01208 We just got YouTube TV recently and also something that is pretty impressive by Google and saves me a ton of money as my cable provider was awful charging for every TV monthly. Another example of something I find really interesting is Spanner. https://research.google.com/archive/spanner.html

Thought one of the more interesting ideas is the Jeff Dean paper on using the TPU for more traditional CS operations like an index lookup. Like to see this progress and get more data on the difference is power required using a CPU and traditional algorithms versus using a TPU and new algorithms like Jeff outlined. https://arxiv.org/abs/1712.01208 The Case for Learned Index Structures