What are the lesser known but cool data structures?

Skip lists and splay trees, two frequent suggestions on this thread, are "lesser known" for a reason: skip lists because for any given skip list implementation there is most probably an encoding of balanced binary trees that outperforms it, even in concurrency, and splay trees because <i>every</i> balanced binary tree outperforms them --- and, in order to avoid writing and testing balancing code, you have to trade off the fact that <i>reading</i> the tree modifies the data structure.<p>Judy arrays came up once too; there's a really excellent critique of Judy arrays here:<p><a href="http://www.nothings.org/computer/judy/" rel="nofollow">http://www.nothings.org/computer/judy/</a><p>(Long story short: you can get comparable performance from a straightforward hash table, and Judy Arrays have to be tuned to the microarchitecture).<p>Favorite data structure not cited here:<p>Aguri trees, which marry a bounded-size radix trie (like you'd use in a software routing table) to an LRU list, and automatically synthesize aggregates (like, 10.0.0.0/16 from 1,000 observations across all IPs) from the pattern of insertion. They're best known in traffic analysis, but we've used them on in runtime memory analysis as well.

Nobody mentioned the unrolled linked list, a simple, useful, and often-overlooked data structure.<p><a href="http://en.wikipedia.org/wiki/Unrolled_linked_list" rel="nofollow">http://en.wikipedia.org/wiki/Unrolled_linked_list</a><p>The idea is the same as a linked list, but instead of just one element in each node, it stores an entire array. This simple change fixes the two biggest problems with linked lists — memory overhead and cache efficiency. It's also easy to tweak to be more "array-like" or more "list-like" as needed.

ZDDs. A ZDD is a DAG of outdegree two where each node represents a set of subsets of some arbitrarily-ordered domain. A node's left child contains all subsets which lack the smallest element in those subsets; its right child contains all subsets which do contain the smallest element.<p>This allows for tremendous compression of search spaces -- one example Knuth gave in a talk I went to a few weeks ago was representing all five-letter words in the English (represented as subsets of {a_1, a_2, ..., z_4, z_5}, where e.g.: {k_1, n_2, u_3, t_4, h_5} represents "knuth"), and efficiently making queries such as finding all words that, when a 'b' is replaced with an 'o', yield another word. More impressive to me was representing all of a certain class of tilings with only a few hundred thousand nodes, when the total number of such tilings was, IIRC, on the order of 10^20.

By far the coolest data structure is the soft heap (<a href="http://www.link.cs.cmu.edu/15859-f07/papers/chazelle-soft-heap.pdf" rel="nofollow">http://www.link.cs.cmu.edu/15859-f07/papers/chazelle-soft-he...</a>).<p>From wikipedia: <a href="http://en.wikipedia.org/wiki/Soft_heap" rel="nofollow">http://en.wikipedia.org/wiki/Soft_heap</a><p>In computer science, the soft heap, designed by Bernard Chazelle in 2000, is a variant on the simple heap data structure. By carefully "corrupting" (increasing) the keys of at most a certain fixed percentage of values in the heap, it is able to achieve amortized constant-time bounds for all five of its operations:

Not sure if kd-trees are lesser known, but they are neat. I only learned about them recently so to me they were "lesser known".<p>"In computer science, a kd-tree (short for k-dimensional tree) is a space-partitioning data structure for organizing points in a k-dimensional space. kd-trees are a useful data structure for several applications, such as searches involving a multidimensional search key (e.g. range searches and nearest neighbor searches). kd-trees are a special case of BSP trees." -- <a href="http://en.wikipedia.org/wiki/Kd-tree" rel="nofollow">http://en.wikipedia.org/wiki/Kd-tree</a>

Nothing makes me want to hire developers like reading lists of algorithms and discovering I don't understand them.

An earlier HN item discussed an interesting one (<a href="http://news.ycombinator.com/item?id=1156628" rel="nofollow">http://news.ycombinator.com/item?id=1156628</a>)

I didn't see any mention of "Threaded Trees": <a href="http://en.wikipedia.org/wiki/Threaded_binary_tree" rel="nofollow">http://en.wikipedia.org/wiki/Threaded_binary_tree</a><p>They're discussed in detail in volume one of Knuth's "The Art of Computer Programming".

it's hard to qualify 'lesser known', I'm not sure if red-black trees qualify, but they're certainly cool:<p><a href="http://en.wikipedia.org/wiki/Red-black_tree" rel="nofollow">http://en.wikipedia.org/wiki/Red-black_tree</a>

The Markov Chain: <a href="http://www.itl.nist.gov/div897/sqg/dads/HTML/markovchain.html" rel="nofollow">http://www.itl.nist.gov/div897/sqg/dads/HTML/markovchain.htm...</a>

I found a lot of the data structures in "Computational Geometry: Algorithms and Applications" interesting

happy to see disjoint sets in there