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

11–20 of 43 posts

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

#11

Post by TimonKnigge »

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…

In the linked article they resolve collisions via chaining:

> A typical hash function distributes keys randomly across the slots in a hash table, causing some slots to be empty, while others have collisions, which require some form of chaining of items

I.e. each field in the table is a linked list of values that hash to this position, and the new value is inserted in the shortest of the two lists it hashes to.

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

#12

Post by dataflow »

throwaway81523 wrote: post #8
dataflow wrote: post #2

Why do cuckoo hashing advertisements always sound like snake oil sales pitches? Claim: "A simple and beautiful technique that can achieve 99% occupancy and serve all lookups with just two memory accesses thanks to the power of two choices." Great, so apparently I can achieve 99% occupancy? Reality [1]: "Insertions succeed in expected constant time [...] as long as the number of keys is kept below half of the capacity…

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?

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

#13

Post by throwaway81523 »

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?

Large perfect hash tables have to store an awful lot of information. I don't remember quite how it's done but it's not a free lunch. The hash function itself has a size that grows with the total size of all the keys.

I don't know offhand how many rehashes you need to get 98% occupancy with cuckoo hashing. There may be ways to optimize it by sharding the table into smaller ones. I'll re-read the wikipedia article when I get a chance. It's a fun algorithm and I've sometimes looked for places to use it.

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

#14

Post by DiabloD3 »

truenindb wrote: post #5
dataflow wrote: post #2

Why do cuckoo hashing advertisements always sound like snake oil sales pitches? Claim: "A simple and beautiful technique that can achieve 99% occupancy and serve all lookups with just two memory accesses thanks to the power of two choices." Great, so apparently I can achieve 99% occupancy? Reality [1]: "Insertions succeed in expected constant time [...] as long as the number of keys is kept below half of the capacity…

It's because the internet is a perfect sterling engine, guaranteeing that all eyeballs will be monotized in an adiabatic flow. It is know as "The Permanent November of ImaginosVictory Law" to those of us that have been using the internet since Salman Rushdie invented email, which is one of the best exemplars of a good protocol since Google Wave.

I don't know who's running a GPT bot on HN, but this is a beautiful work of art.

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

#15

Post by eutectic »

TimonKnigge wrote: post #11
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…

In the linked article they resolve collisions via chaining: > A typical hash function distributes keys randomly across the slots in a hash table, causing some slots to be empty, while others have collisions, which require some form of chaining of items I.e. each field in the table is a linked list of values that hash to this position, and the new value is inserted in the shortest of the two lists it hashes to.

No, chaining is presented as an alternative to Cuckoo hashing.

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

#16

Post by orf »

lrem wrote: post #7
truenindb wrote: post #5

Earlier quoted context omitted.

It's because the internet is a perfect sterling engine, guaranteeing that all eyeballs will be monotized in an adiabatic flow. It is know as "The Permanent November of ImaginosVictory Law" to those of us that have been using the internet since Salman Rushdie invented email, which is one of the best exemplars of a good protocol since Google Wave.

Was this generated with some GPT3-like or something?

I think so, the only result on Google for “ ImaginosVictory” is that very comment.

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

#17

Post by [deleted] »

dataflow wrote: post #2

Why do cuckoo hashing advertisements always sound like snake oil sales pitches? Claim: "A simple and beautiful technique that can achieve 99% occupancy and serve all lookups with just two memory accesses thanks to the power of two choices." Great, so apparently I can achieve 99% occupancy? Reality [1]: "Insertions succeed in expected constant time [...] as long as the number of keys is kept below half of the capacity…

[deleted]

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

#18

Post by FreakLegion »

dataflow wrote: post #2

Why do cuckoo hashing advertisements always sound like snake oil sales pitches? Claim: "A simple and beautiful technique that can achieve 99% occupancy and serve all lookups with just two memory accesses thanks to the power of two choices." Great, so apparently I can achieve 99% occupancy? Reality [1]: "Insertions succeed in expected constant time [...] as long as the number of keys is kept below half of the capacity…

> 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 capacity of 2 already yields > 96% occupancy, and 4 reaches 99.9%, so smaller and faster (lookups examine fewer keys on average). This approach is detailed in "3.5-Way Cuckoo Hashing for the Price of 2-and-a-Bit".

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

#19

Post by dataflow »

FreakLegion wrote: post #18
dataflow wrote: post #2

Why do cuckoo hashing advertisements always sound like snake oil sales pitches? Claim: "A simple and beautiful technique that can achieve 99% occupancy and serve all lookups with just two memory accesses thanks to the power of two choices." Great, so apparently I can achieve 99% occupancy? Reality [1]: "Insertions succeed in expected constant time [...] as long as the number of keys is kept below half of the capacity…

> 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?

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

#20

Post by toxik »

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.
Post reply on HN