4 ms·
The learned index paper struck me as a bit of a marketing gimmick, but this paper also smells a bit. The central sleight of hand that both papers pull without
by pclmulqdq 5y ago
The learned index paper struck me as a bit of a marketing gimmick, but this paper also smells a bit. The central sleight of hand that both papers pull without admitting it is that they are creating mostly-read data structures (or in the first half of the learned index paper, read-only data structures). The learned index paper then compares them to read-write data structures and claims a win.
Due to cache locality, cuckoo hashing usually underperforms compared to linear probing hash tables, except when you want super high density and you don't expect to do much inserting. It gets especially bad if the keys or values are large. 99% of the time, you're better off with something other than cuckoo hashing.
- resters 5y agoLearned indexes are an optimization technique that can help a lot in specific scenarios, but the authors were not under the impression that they are applicable to most use-cases.
- thesz 5y agoLogarithmic method can transform static structures (what you call read-only, which means high cost of change) into dynamic ones. Examples include B-trees (log structured merge trees, the most famous example of application of logarithmic method), kd-trees, sorted arrays (cache oblivious lookahead arrays - COLA) and more. Usually, some variant of merge operation is much more efficient than application of changes. It is obvious for sorted arrays (merge sort). It is true for kd-trees - they can be efficiently constructed from sorted data and it is easy to fetch sorted data from kd-trees. It is also quite true for B-trees. B-trees degrade when under random data load (and hugely so), but they are doing well when changes are in order. Log structured merge trees make static (under random data load) B-trees dynamic again. The merge operation for learned indices is, well, learning from two sources and merge information. My not so big experience with machine learning tells me that adjusting model is easier than training it anew.