Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Classical data structures that can outperform learned indexes (2018)

dawn.cs.stanford.edu

Post reply on HN
Print view View original

31–40 of 43 posts

Re: Classical data structures that can outperform learned indexes (2018)

#31

Post by phkahler »

dataflow wrote: post #19
FreakLegion wrote: post #18

Earlier quoted context omitted.

> Ok so never mind... Keep reading, specifically the Variations section. 50% occupancy is for constructions with a per-bucket capacity of 1. At a capacity of 2, occupancy improves to a little under 90%, and at 4 to just under 98%. The linked write-up uses 8, which does in fact achieve very high occupancy. They could've done better, though. By using windows instead of buckets (i.e. allowing the buckets to overlap), a…

Thanks, that explains what they're saying now. But I'm still skeptical. How achievable is 98% fill for 4-element buckets in the first place? Intuitively I feel like you'd frequently have to scrap the table and rehash or enlarge it... is that not the case?

Seems like a good point. If you're at 90+ percent occupancy you're going to run into trouble adding more data.

Re: Classical data structures that can outperform learned indexes (2018)

#32

Post by phkahler »

touisteur wrote: post #24
toxik wrote: post #23

Earlier quoted context omitted.

They do in fact not have erratic behavior, they are quite predictable. The cuckooing process, on the other hand, is not predictable by design.

Recently went on a deep dive about sorting algorithm actual predictability and for latency-sensitive workloads, most things you'd use because 'simple/standard' (quicksort, mergesort...) don't shine, with their horrid /worst case/ complexity, but also depending a lot on your input data. Quicksort with a badly chosen pivot, for example, has caused me headaches recently.

Heapsort is O(n * Log(n)) worst case. It is also O(n * Log(n)) in most cases, including already sorted data. Most implementations also seem to have a slightly larger constant factor than quicksort, but I think that's largely due to implementation details (one should not actually swap values that are likely to be immediately swapped again).

Which one is right really does come down to a decision based on how much you care about Typical/Average/WorstCase time complexity and the actual size of your data set.

Re: Classical data structures that can outperform learned indexes (2018)

#33

Post by jcelerier »

adrianN wrote: post #22
toxik wrote: post #20

Earlier quoted context omitted.

Ah, O(wildly erratic) insertion. Great for that jittery feel to your programs.

Most popular data structures only provide average case guarantees with bad worst-case bounds. Dynamic arrays also have O(wildly erratic) append. I think for most use cases this is perfectly fine and does not result in any perceivable jitter in programs.

> I think for most use cases this is perfectly fine and does not result in any perceivable jitter in programs.

we must not use the same programs :-(

Re: Classical data structures that can outperform learned indexes (2018)

#34

Post by jasonwatkinspdx »

dataflow wrote: post #19
FreakLegion wrote: post #18

Earlier quoted context omitted.

> Ok so never mind... Keep reading, specifically the Variations section. 50% occupancy is for constructions with a per-bucket capacity of 1. At a capacity of 2, occupancy improves to a little under 90%, and at 4 to just under 98%. The linked write-up uses 8, which does in fact achieve very high occupancy. They could've done better, though. By using windows instead of buckets (i.e. allowing the buckets to overlap), a…

Thanks, that explains what they're saying now. But I'm still skeptical. How achievable is 98% fill for 4-element buckets in the first place? Intuitively I feel like you'd frequently have to scrap the table and rehash or enlarge it... is that not the case?

So, for the complete formal answer get Mitzenmacher's book: https://www.amazon.com/Probability-Computing-Randomized-Algo...

There are incrementally resizing versions, generally under the name Levelized Hashing. The most state of the art versions of these are lock free. (example: https://www.usenix.org/conference/atc20/presentation/chen)

Re: Classical data structures that can outperform learned indexes (2018)

#36

Post by thesz »

pclmulqdq wrote: post #25

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, cu…

Logarithmic 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.

Re: Classical data structures that can outperform learned indexes (2018)

#37

Post by nullc »

toxik wrote: post #20
the_duke wrote: post #4

It wasn't clear to me how Cuckoo hash tables are supposed to work if both locations are full. Here is the relevant explanation from Wikipedia : > The new key is inserted in one of its two possible locations, "kicking out", that is, displacing, any key that might already reside in this location. This displaced key is then inserted in its alternative location, again kicking out any key that might reside there. The proc…

Ah, O(wildly erratic) insertion. Great for that jittery feel to your programs.

A below transition fullness the insertion process takes N kicks with exponentially decreasing probability (for some constants depending on the fullness level and number of hash functions). E.g. 1/2^n kicks.

Not something you can really describe as wildly erratic.

If latency is particularly critical in your application, you could couple the hash table with a small "stash" map and perform a constant maximum number of kicks per insert, and when you reach the limit stick the current straggler in the map to be continued on the next insertion. As long as the constant maximum is well above the average the map will stay empty most of the time.

Re: Classical data structures that can outperform learned indexes (2018)

#38

Post by nullc »

dataflow wrote: post #12
throwaway81523 wrote: post #8

Earlier quoted context omitted.

IIRC you can get to high occupancy by doing enough rehashes. After that, if you do no more insertions and only lookups, it is a good deal since each lookup takes at most two memory accesses. So this is useful if you are willing to spend a long time building what will then be a read-only table. Obviously there are uses for that.

> IIRC you can get to high occupancy by doing enough rehashes. Yeah so how many total insertions (as part of the rehashing) do you expect to have to do to achieve 99% occupancy? Wouldn't it be even worse than O(n^2)? And if you're going to spend a lot of time rebuilding the hash table all the time, then why not just use a perfect hash generator?

> Yeah so how many total insertions (as part of the rehashing) do you expect to have to do to achieve 99% occupancy? Wouldn't it be even worse than

It depends on your bucket sizes and how many hashes you use.

If you attempt 99% occupancy with 2 hashes and 4 entries per bucket, then you are going to be doing a LOT of kicking. 92% with that geometry, OTOH, is fine and will end up with just a couple kicks per insert on average.

Re: Classical data structures that can outperform learned indexes (2018)

#39

Post by toxik »

nullc wrote: post #37
toxik wrote: post #20

Earlier quoted context omitted.

Ah, O(wildly erratic) insertion. Great for that jittery feel to your programs.

A below transition fullness the insertion process takes N kicks with exponentially decreasing probability (for some constants depending on the fullness level and number of hash functions). E.g. 1/2^n kicks. Not something you can really describe as wildly erratic. If latency is particularly critical in your application, you could couple the hash table with a small "stash" map and perform a constant maximum number of k…

The fact that you're talking about probabilities sort of proves my point. You're instead saying it could be worse, and I'm saying random execution times in your critical paths is generally undesirable. It depends on your application of course, but if you have anything realtime or near realtime, I would definitely take consistent execution times.

There is a related e-mail from IdSoft's John Carmack about this at [1] which I found very interesting.

[1] http://number-none.com/blow/blog/programming/2014/09/26/carm...

Re: Classical data structures that can outperform learned indexes (2018)

#40

Post by rurban »

And modern data structures always outperform classical ones.

Why cuckoo when you usually use swiss tables or stanford tables for longs? Or https://greg7mdp.github.io/parallel-hashmap/ for concurrent htables?

Learned indices (ie dynamic data structures optimized to the data) usually outperform these as well if they are properly optimized. Which can be neural nets, but also perfect hashes or just better dynamic lookup methods. Like three-way array lookups, properly compressed, as with Unicode. Not everything needs to be a NN, though it helps if you see no structure in the data.

Post reply on HN