Nested Set Model: a way to model nested sets of entities and query them in a SQL database. I haven't used it for anything but it seems fun. https://en.m.wikipedia.org/wiki/Nested_set_model
Used it for tag hierarchy, liked it a lot!
Ask HN: What are some cool but obscure data structures you know about?
111–120 of 772 posts
Re: Ask HN: What are some cool but obscure data structures you know about?
#112I’ve bookmarked this thread. I have a new reading list! Thanks OP!
Re: Ask HN: What are some cool but obscure data structures you know about?
#113Fountain Codes: reconstruct data from random selection of packets.
Was deeply patent encumbered until recently.
Re: Ask HN: What are some cool but obscure data structures you know about?
#114Earlier quoted context omitted.
You forgot the most important feature over normal hash maps: they offer a deterministic iteration order without incurring the cost of a tree-based ordered map. (If you don't know why this is important then maybe you haven't worked on large systems that undergo rigorous evaluation)
Is (non-)determinism really the right concern here? I’m aware that most hash tables do not have generally predictable iteration orders, but I nevertheless understood them to be deterministic.
They are deterministic in the sense that provided everything else is the same, iteration order would be the same after each insertion.
However, it can change after insertion (if the hash bucket count changes). If the hash function is random-keyed, iteration order would be different for different instances of the hash table even if you insert the same items in the same order.
Sometimes you want the order to be consistent every time. Be it insertion order, or some natural order of the items.
Re: Ask HN: What are some cool but obscure data structures you know about?
#115Finger trees allow you to do amazing things. In essence they let you build an index, or multiple indices, for your dataset and then store them in a single structure. When I go from Haskell back to imperative land I find myself greatly missing this ability. Sure I can make multiple hashmaps or trees or whatever but being able to stuff it all in one data structure is amazing. One structure I built with them that is muc…
You might enjoy a paper I’m a coauthor on which combines finger trees with B-trees to build a data structure for optimal updates to sliding windows: Optimal and General Out-of-Order Sliding-Window Aggregation, https://www.scott-a-s.com/files/vldb2019_fiba.pdf
Slides from the conference talk: https://www.scott-a-s.com/files/vldb2019_fiba_slides.pdf
Re: Ask HN: What are some cool but obscure data structures you know about?
#116Structures good for Geospatial information like rtrees, quadtrees. https://en.m.wikipedia.org/wiki/R-tree Also concurrent data structures. https://youtu.be/jcqGSehrMGU
Also LSM trees!
Re: Ask HN: What are some cool but obscure data structures you know about?
#117Earlier quoted context omitted.
Funny you should mention bloom filters and that use case, I just re-read this post again this morning: https://blog.cloudflare.com/when-bloom-filters-dont-bloom/ Basically, it makes a similar point to https://news.ycombinator.com/item?id=32186837 — i.e., cache effects are not modeled in big O analysis, even though most problems that involve large amounts of data (so most problems) are memory bound rather than CPU bou…
That Cloudflare article is a little frustrating. > While we could think of more sophisticated data structures like Cuckoo filter, maybe we can be simpler Yes, standard Bloom filters fail for large filter sizes and/or very small false-positive rates. But we've known this for decades, and tons of other probabilistic filters have come out since then to address the problem. Cuckoo filters in particular are incredible. Wa…
[deleted]
Re: Ask HN: What are some cool but obscure data structures you know about?
#118The Suffix Array is surprisingly cool and useful https://en.wikipedia.org/wiki/Suffix_array The Alias Table for sampling a discrete distribution in O(1) time is a very clever idea https://www.keithschwarz.com/darts-dice-coins/
The fact that suffix trees/suffix arrays can be built in O(n) is IMO the most surprising and "magical" result in computer science. To me, more surprising than median of medians/quick select. There might be more "magical"/surprising things that are obscure and I am unaware of, but to me, this is it. :)
what about randomized O(n) minimum spanning trees?
Re: Ask HN: What are some cool but obscure data structures you know about?
#119Earlier quoted context omitted.
Funny you should mention bloom filters and that use case, I just re-read this post again this morning: https://blog.cloudflare.com/when-bloom-filters-dont-bloom/ Basically, it makes a similar point to https://news.ycombinator.com/item?id=32186837 — i.e., cache effects are not modeled in big O analysis, even though most problems that involve large amounts of data (so most problems) are memory bound rather than CPU bou…
That Cloudflare article is a little frustrating. > While we could think of more sophisticated data structures like Cuckoo filter, maybe we can be simpler Yes, standard Bloom filters fail for large filter sizes and/or very small false-positive rates. But we've known this for decades, and tons of other probabilistic filters have come out since then to address the problem. Cuckoo filters in particular are incredible. Wa…
A linear probing hash table is simpler. That’s the trade off they were going for at that time. I don’t think that’s the most efficient solution given the hardware they were using, and I don’t think the blog author would either, but it’s certainly easier to write such a hash table — and it’s well written, but still mostly interview level stuff.
To me the blog post is not about cuckoo or bloom filters or hash tables at all. It’s about profiling and highlighting that a naive reading of the literature can easily lead you astray (worse performance and complexity). In school they don’t teach you that mov is the biggest cycle-eater of them all — at least it’s not the lesson people remember.
Re: Ask HN: What are some cool but obscure data structures you know about?
#120Monotonic stacks are neat. I made up a data structure once, consisting of a pyramid of deques. It lets you efficiently compute any associative function over a streaming window of data.
You may be interested in the work myself and some coauthors have done on data structures and algorithms for streaming aggregation. GitHub repo for the code, which high level descriptions of their properties and pointers to papers: https://github.com/IBM/sliding-window-aggregators