Three of my favorite probabilistic data structures are: Skip Lists, Bloom Filters, and SimHashes.
Ask HN: What are some cool but obscure data structures you know about?
11–20 of 772 posts
Re: Ask HN: What are some cool but obscure data structures you know about?
#12Finger 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 much more difficult with typical structures is a "block list" structure.
In this structure each block has a particular width and they're all stacked side by side.
I want to perform a query, "which box is at position X". So if my boxes are of widths 7,20,10, then the lookup for 2 yields the first box, the lookup for 12 yields the second, etc.
More interestingly, if add a new box between the second and third, the indices covered by the last box is increased.
With finger trees you use a sum monoid. This is easy. In other languages you have to roll your own structure either using a list (with o(n) lookup) or a tree with o(log n) lookup, but o(n) inserts (to translate the indices of future blocks)
Re: Ask HN: What are some cool but obscure data structures you know about?
#13Linked Hash/Tree Maps, simple, but elegant. A Map with its nodes connected in a linked list so you can traverse them in insertion order (and O(n) time). Very useful for window queries over sequential data and other cases where you want FIFO access, but also quick access by a field of the data.
Re: Ask HN: What are some cool but obscure data structures you know about?
#14The Israeli queue. Like a regular queue, but if something new that comes in sees its friend in the queue already, it can jump the queue and go and stand next to her. Useful for when something has a big overhead on top of its own processing, but the overhead can be shared between several similar entries. If you're doing it anyway for the one already in the queue, you get to make the most of it for its friends too. I c…
Sounds like a priority queue
Re: Ask HN: What are some cool but obscure data structures you know about?
#15All probabilistic structures are fascinating to me. I'm most enamored with HyperLogLog - estimating the number of distinct elements in extremely large sets of data without having to build a set of seen elements - but the entire field is pretty awesome.
The canonical use case for HLL is counting unique visitors. But any large dataset where you only need a good approximation is a valid target :)
Re: Ask HN: What are some cool but obscure data structures you know about?
#16Monotonic 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.
I recently learned about monotonic stacks thanks to this LeetCode problem: https://leetcode.com/problems/sum-of-total-strength-of-wizar...
I feel like they're quite possibly the most deceptively simple data structure I've yet to encounter. That is to say that for me at least there was/is a wide gulf between simply understanding what the data structure is (doesn't get much simpler than a stack!) and when/how to actually apply it.
Re: Ask HN: What are some cool but obscure data structures you know about?
#17The LIFO buffer. Also surfaces as the messy desk, the million email inbox, or ten-thousand browser tabs. It really works at progressively sorting frequently accessed items to the top, even accounting for changing or seasonal habits and preferences.
Re: Ask HN: What are some cool but obscure data structures you know about?
#18Structures good for Geospatial information like rtrees, quadtrees.
https://en.m.wikipedia.org/wiki/R-tree
Also concurrent data structures.
Re: Ask HN: What are some cool but obscure data structures you know about?
#19Tries (or prefix trees). We use them a lot at Pyroscope for compressing strings that have common prefixes. They are also used in databases (e.g indexes in Mongo) or file formats (e.g debug symbols in macOS/iOS Mach-O format are compressed using tries). We have an article with some animations that illustrate the concept in case anyone's interested [0]. [0] https://github.com/pyroscope-io/pyroscope/blob/main/docs/sto..…
I wouldn't consider tries to be obscure tbh. They are the recommended solution for many leetcode-style interview problems involving string searching. I think anyone who has done serious interview prep has encountered them.
https://leetcode.com/discuss/general-discussion/931977/begin...
Re: Ask HN: What are some cool but obscure data structures you know about?
#20The Israeli queue. Like a regular queue, but if something new that comes in sees its friend in the queue already, it can jump the queue and go and stand next to her. Useful for when something has a big overhead on top of its own processing, but the overhead can be shared between several similar entries. If you're doing it anyway for the one already in the queue, you get to make the most of it for its friends too. I c…
How do you implement it? Do you do a scan with every insert or do you hash or use a tree for indexing?