[HN Gopher] Classical data structures that can outperform learne...
___________________________________________________________________
Classical data structures that can outperform learned indexes
(2018)
Author : signa11
Score : 241 points
Date : 2021-08-16 06:21 UTC (16 hours ago)
(HTM) web link (dawn.cs.stanford.edu)
(TXT) w3m dump (dawn.cs.stanford.edu)
| dang wrote:
| Discussed at the time:
|
| _Classical Data Structures That Can Outperform Learned Indexes_
| - https://news.ycombinator.com/item?id=16138857 - Jan 2018 (20
| comments)
| anonu wrote:
| Another great lesson that you can't slap "AI" on everything...
| pclmulqdq wrote:
| 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.
| thesz wrote:
| 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.
| resters wrote:
| Learned 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.
| dataflow wrote:
| 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 of the hash table, i.e., _the load factor is below 50%_.
| "
|
| Ok so never mind...
|
| [1] https://en.wikipedia.org/wiki/Cuckoo_hashing#Theory
| truenindb wrote:
| 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.
| xarope wrote:
| bingo?
| lrem wrote:
| Was this generated with some GPT3-like or something?
| orf wrote:
| I think so, the only result on Google for "
| ImaginosVictory" is that very comment.
| chana_masala wrote:
| Do you have an ICO I buy into?
| DiabloD3 wrote:
| I don't know who's running a GPT bot on HN, but this is a
| beautiful work of art.
| throwaway81523 wrote:
| 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.
| dataflow wrote:
| > 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?
| throwaway81523 wrote:
| 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.
| signa11 wrote:
| 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 ?
| [deleted]
| FreakLegion wrote:
| > _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".
| dataflow wrote:
| 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?
| jasonwatkinspdx wrote:
| 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)
| phkahler wrote:
| Seems like a good point. If you're at 90+ percent occupancy
| you're going to run into trouble adding more data.
| dicroce wrote:
| As I read this I thought "interesting. I would have thought
| probing would be better on modern computers with memory pre-
| fetching"... Then I come to the comments and find out im not the
| only one thinking that.
| pclmulqdq wrote:
| You're right, benchmarks have shown that probing is better
| until you reach ~90% capacity. Cuckoo hashing sufferers from
| terrible memory locality, and you can only make up for it when
| a probing table would have worse locality.
| truenindb wrote:
| Look 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...
| the_duke wrote:
| 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 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.
| toxik wrote:
| Ah, O(wildly erratic) insertion. Great for that jittery feel to
| your programs.
| j-pb wrote:
| Since you double the table size after failing to
| insert/displace above a constant threshhold, e.g. 8. You have
| O(1) insert performance. You don't need to rehash the table
| either, you can add additional hash functions on each grow,
| or reuse your existing hash function and use bit masking,
| (that one does require a copy of the table, albeit no
| rehashing, and copying chunks is something our CPUs are
| really good at)
| adrianN wrote:
| 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.
| toxik wrote:
| They do in fact not have erratic behavior, they are quite
| predictable. The cuckooing process, on the other hand, is
| not predictable by design.
| touisteur wrote:
| 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.
| karpierz wrote:
| Mergesort worst case is O(nlog(n)). If there's a downside
| to it, it's that you need to allocate memory.
| phkahler wrote:
| 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.
| jcelerier wrote:
| > 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 :-(
| TimonKnigge wrote:
| 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.
| eutectic wrote:
| No, chaining is presented as an alternative to Cuckoo
| hashing.
___________________________________________________________________
(page generated 2021-08-16 23:02 UTC)