Classical data structures that can outperform learned indexes (2018)
dawn.cs.stanford.edu
Classical data structures that can outperform learned indexes (2018)
1–10 of 43 posts
Re: Classical data structures that can outperform learned indexes (2018)
#2Why 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 of the hash table, i.e., the load factor is below 50%."
Ok so never mind...
Re: Classical data structures that can outperform learned indexes (2018)
#3Look you don't need to learn any algorithms because SQL will allow the computer to algorithm for you. SQL will guarantee ACID properties and also BASE properties. You are going to be rich. Simply buy Larry Ellison a boat and a bunch of ads on the back of the economist to socially prove to the finance world and the folks from Dave Graeber's actually very good essay that has not yet been followed up with the great american novel, and you are gonna be rich with no algorithms not done by the computer.
Don't worry, the computer is gonna take care of it, you won't need handwriting or food.
Here is a link to Mr. Graeber's high quality novel, "On the phenomenon of bullshit jobs": https://www.theatlantic.com/magazine/archive/2004/07/i-agree...
Re: Classical data structures that can outperform learned indexes (2018)
#4It 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 process continues in the same way until an empty position is found, completing the algorithm. However, it is possible for this insertion process to fail, by entering an infinite loop or by finding a very long chain (longer than a preset threshold that is logarithmic in the table size). In this case, the hash table is rebuilt in-place using new hash functions
https://en.wikipedia.org/wiki/Cuckoo_hashing#Operation
Sound like with high occupancy the table would need to be rebuilt constantly.
Re: Classical data structures that can outperform learned indexes (2018)
#5Why 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.
Re: Classical data structures that can outperform learned indexes (2018)
#6Why 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.
bingo?
Re: Classical data structures that can outperform learned indexes (2018)
#7Why 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.
Was this generated with some GPT3-like or something?
Re: Classical data structures that can outperform learned indexes (2018)
#8Why 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.
Re: Classical data structures that can outperform learned indexes (2018)
#9Why 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…
i found this (https://codecapsule.com/?s=hashing) to be quite instructive as an overview of various hashing techniques. check it out for some fun ?
Re: Classical data structures that can outperform learned indexes (2018)
#10Why 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.
Do you have an ICO I buy into?