11 ms·

What are the lesser known but cool data structures?

174 points by limist 16y ago

tptacek 16y ago
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 every balanced binary tree outperforms them --- and, in order to avoid writing and testing balancing code, you have to trade off the fact that reading the tree modifies the data structure. Judy arrays came up once too; there's a really excellent critique of Judy arrays here: http://www.nothings.org/computer/judy/ http://www.nothings.org/computer/judy/ (Long story short: you can get comparable performance from a straightforward hash table, and Judy Arrays have to be tuned to the microarchitecture). Favorite data structure not cited here: 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.
- sesqu 16y ago
  for any given skip list implementation there is most probably an encoding of balanced binary trees that outperforms it Not just probably, absolutely. Skip lists are probably pretty balanced, which is always less balanced than actually pretty balanced. Their sole claim to fame is their simplicity in implementation compared to actual self-balancing trees.
  - tptacek 16y ago
    You can find blog posts and Stack Overflow articles talking about lock overhead in rb-trees versus skip lists, and just looking at a diagram you can intuitively sense where that idea comes from. But these kinds of analyses are usually flawed by the fact that they assume the most naive possible encoding of tree edges (void* tree* tree*).
    - jey 16y ago
      Hm, what are some conncurrency-friendly ways to encode tree edges?
      - tptacek 16y ago
        I don't have an answer for you (I'm just making the point that when people argue about how inefficient trees are, they're usually assuming a struct with two edge pointers), but a more direct answer to your question might be: http://www.cl.cam.ac.uk/research/srg/netos/lock-free/ http://www.cl.cam.ac.uk/research/srg/netos/lock-free/ (That's a lock-free red-black tree impl).
  - pjscott 16y ago
    Not so! There's one thing you can do with skip lists that I don't know of any easy way to do with other data structures. Suppose you want a priority queue, and you have a bunch of cores, and these cores want to insert into the queue and remove the minimum element concurrently. How do you implement this to allow fast concurrent access from a lot of threads? First, there's the approach everybody remembers from Intro to Algorithms: use a binary min-heap. It's guaranteed to be balanced, so you get O(lg n) time insertions and delete-the-minimum operations, with low constant factors. Nice! But how do you make it concurrent? You can put a lock on the whole thing and only let one thread use it at once, but that's slow. You could use fancy fine-grained locking, but there will still be inter-thread memory conflicts arising from the heapify operations you need to maintain the heap invariant. There has been some work on this, and they've come up with some decent ideas, but it still has scaling problems. Now look at skip lists. It's a randomized sorted list data structure, and it claims to be, as you put it, probably pretty balanced. Various threads can insert concurrently without breaking that "probably pretty balanced" property. The memory read- and write-sets are very local, and it's possible to do all this with lock-free synchronization. The end result is a priority queue data structure that scales to hundreds of cores. And the code doesn't fry your brain, which is a plus. There's a pretty neat paper about it here: http://www-cs-students.stanford.edu/~itayl/ipdps.pdf http://www-cs-students.stanford.edu/~itayl/ipdps.pdf By the way, if you happen to be using a processor with hardware transactional memory support (you aren't, yet), then this code becomes even easier to write, as you don't have to worry about how to do lock-free synchronization. I almost felt cheated by how simple it was.
    - jamii 16y ago
      The general lesson is that randomized algorithms often remove the need for synchronization between concurrent processes. For example, choosing ids at random from a large space rather than coordinating to choose unique ids.
    - scott_s 16y ago
      What and where are you working that you have access to a processor with hardware transactional memory support?
- xtacy 16y ago
  An interesting application of skip lists: http://www.skorks.com/2010/03/faster-list-intersection-using-skip-pointers/ http://www.skorks.com/2010/03/faster-list-intersection-using... But I can't see why the same cannot be done using trees. :-/
panic 16y ago
Nobody mentioned the unrolled linked list, a simple, useful, and often-overlooked data structure. http://en.wikipedia.org/wiki/Unrolled_linked_list http://en.wikipedia.org/wiki/Unrolled_linked_list 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.
- sjf 16y ago
  Hah, I never knew there was a name for it, thanks.
- jules 16y ago
  An interesting variation on this is the VList, which works the same way except the inner arrays have variable size. This gives you an asymptotic rather than constant speedup for many operations. http://en.wikipedia.org/wiki/VList http://en.wikipedia.org/wiki/VList
- Retric 16y ago
  Yep, unrolled liked lists often work great for sparse 2D data structures especially when you get a lot of clustering around small areas. (think spreadsheets)
- pjscott 16y ago
  At one point, Python tried to move to something similar for their standard list data structure: http://www.python.org/dev/peps/pep-3128/ http://www.python.org/dev/peps/pep-3128/ The BList is similar to a B+Tree. It was meant to act like an array for small lists, but to make operations like append, concatenation, and slicing faster. It was a pretty cool combination of arrays (for memory compactness and good cache performance and small constant factors) with trees, for the asymptotic improvements they can bring. Sadly, it didn't take off, as it would have broken backward compatibility with extension modules.
  - _delirium 16y ago
seldo 16y ago
Nothing makes me want to hire developers like reading lists of algorithms and discovering I don't understand them.
- araneae 16y ago
  How much effort do you put into understanding them? As with everything, the more complicated something is (or the further away things are from what you're familiar with) the more you have to put into it. If you're interested in understanding them, I recommend finding another source for the explanation, like Wikipedia. The ones on stackoverflow can be a little short for an adequate explanation. Also, there's a limit to how much you can understand by just reading something. Try drawing it out. And in the end, I'm not sure how much understanding this stuff relates to your need for developers, depending on what you're doing. Most web programming involves getting cogs to fit with other cogs, not advanced algorithms. Obscure data structures are generally obscure for a reason; they're more an intellectual curiosity than anything else ^-^.
  - jacquesm 16y ago
    > Obscure data structures are generally obscure for a reason; they're more an intellectual curiosity than anything else ^-^. I don't think that's necessarily true, the problem is that there are so many of them. Consider woodworking. A good woodworker has an absolutely enormous array of tools, and all a woodworker does, if you think about it with the mindset of a non-woodworker is remove bits of wood from other bits of wood and put them back together again. Algorithms are the tools in the toolbox of the programmer, all we do is transform series of bits in to other series of bits. But the number of algorithms is huge compared to the number of tools a woodworker uses, and it is impossible to remember all of them, to pick the one that is 'most appropriate' for the problem at hand. So we may end up using a sub-optimal solution quite a few times when one of the 'obscure' algorithms would have been more appropriate, just because computers are for the most part fast enough to cover for the inefficiencies.
    - seldo 16y ago
      To extend your analogy though, obscure algorithms could be like the techniques that allow master craftsmen to build beautiful, solid furniture using only careful joins and maybe light wood glue. On the other hand, what most people want is something quickly and cheaply assembled from standard parts from IKEA.
ljlolel 16y ago
By far the coolest data structure is the soft heap (http://www.link.cs.cmu.edu/15859-f07/papers/chazelle-soft-heap.pdf http://www.link.cs.cmu.edu/15859-f07/papers/chazelle-soft-he...). From wikipedia: http://en.wikipedia.org/wiki/Soft_heap http://en.wikipedia.org/wiki/Soft_heap 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:
- igravious 16y ago
  Off-topic but meh. The guy is a frighteningly funny and shrewd to boot. See any of his posts at A Tiny Revolution http://www.tinyrevolution.com/mt/ http://www.tinyrevolution.com/mt/ Oh a thanks for the heads-up on this data structure ljlolel.
argv_empty 16y ago
An earlier HN item discussed an interesting one (http://news.ycombinator.com/item?id=1156628 http://news.ycombinator.com/item?id=1156628)
RodgerTheGreat 16y ago
I didn't see any mention of "Threaded Trees": http://en.wikipedia.org/wiki/Threaded_binary_tree http://en.wikipedia.org/wiki/Threaded_binary_tree They're discussed in detail in volume one of Knuth's "The Art of Computer Programming".
jacquesm 16y ago
it's hard to qualify 'lesser known', I'm not sure if red-black trees qualify, but they're certainly cool: http://en.wikipedia.org/wiki/Red-black_tree http://en.wikipedia.org/wiki/Red-black_tree
- pjscott 16y ago
  I like relaxed balanced red-black trees. In those, you're allowed to violate the balancing conditions; you can go back and fix the violations later. This is useful if you want to use them concurrently. The balancing transformations tend to cause lots of contention between threads, so deferring that rebalancing for a later, clean-up thread can really help with scalability.
  - jacquesm 16y ago
    I only learned about this fairly recently: http://www.itl.nist.gov/div897/sqg/dads/ http://www.itl.nist.gov/div897/sqg/dads/ And I feel pretty stupid for not having realized earlier that something like that almost has to exist.
    - pjscott 16y ago
      Heh; it hit me that way, too. It seems obvious in retrospect. I found that this page has a nice mini-introduction: http://www.imada.sdu.dk/~kslarsen/RelBal/ http://www.imada.sdu.dk/~kslarsen/RelBal/ If requests that use a red-black tree tend to come in bursts, then you can probably get speedups by deferring rebalancing for idle periods, even single-threaded. That's pretty darn cool. I would like to see some programming language runtime that watched rb-tree access patterns and decided if this would be a good idea at runtime.
- scott_s 16y ago
  I was under the impression that most balanced binary trees were red-black trees. I know most C++ STL std::map implementations are red-black trees, as is Java's TreeMap.
Darmani 16y ago
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. 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.
- jules 16y ago
  It's not all good however. Try representing all valid Sudokus with a ZDD
sjs 16y ago
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". "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." -- http://en.wikipedia.org/wiki/Kd-tree http://en.wikipedia.org/wiki/Kd-tree
- cloudkj 16y ago
  I second kd-trees. I also only recently learned them, and at first encounter thought that they are in concept similar to binary space partitions used in computer graphics. Nearest neighbor search can be implemented using a pretty simple two-dimensional kd-tree. Useful for things like finding the n closest neighboring points for a given point on a plane (used for mapping applications, etc.)
budwin 16y ago
happy to see disjoint sets in there
ulvund 16y ago
I found a lot of the data structures in "Computational Geometry: Algorithms and Applications" interesting
jperras 16y ago
The Markov Chain: http://www.itl.nist.gov/div897/sqg/dads/HTML/markovchain.html http://www.itl.nist.gov/div897/sqg/dads/HTML/markovchain.htm...

174 points by limist 16y ago

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 every balanced binary tree outperforms them --- and, in order to avoid writing and testing balancing code, you have to trade off the fact that reading the tree modifies the data structure. Judy arrays came up once too; there's a really excellent critique of Judy arrays here: http://www.nothings.org/computer/judy/ http://www.nothings.org/computer/judy/ (Long story short: you can get comparable performance from a straightforward hash table, and Judy Arrays have to be tuned to the microarchitecture). Favorite data structure not cited here: 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.

sesqu 16y ago
for any given skip list implementation there is most probably an encoding of balanced binary trees that outperforms it Not just probably, absolutely. Skip lists are probably pretty balanced, which is always less balanced than actually pretty balanced. Their sole claim to fame is their simplicity in implementation compared to actual self-balancing trees.
- tptacek 16y ago
  You can find blog posts and Stack Overflow articles talking about lock overhead in rb-trees versus skip lists, and just looking at a diagram you can intuitively sense where that idea comes from. But these kinds of analyses are usually flawed by the fact that they assume the most naive possible encoding of tree edges (void* tree* tree*).
  - jey 16y ago
    Hm, what are some conncurrency-friendly ways to encode tree edges?
    - tptacek 16y ago
      I don't have an answer for you (I'm just making the point that when people argue about how inefficient trees are, they're usually assuming a struct with two edge pointers), but a more direct answer to your question might be: http://www.cl.cam.ac.uk/research/srg/netos/lock-free/ http://www.cl.cam.ac.uk/research/srg/netos/lock-free/ (That's a lock-free red-black tree impl).
- pjscott 16y ago
  Not so! There's one thing you can do with skip lists that I don't know of any easy way to do with other data structures. Suppose you want a priority queue, and you have a bunch of cores, and these cores want to insert into the queue and remove the minimum element concurrently. How do you implement this to allow fast concurrent access from a lot of threads? First, there's the approach everybody remembers from Intro to Algorithms: use a binary min-heap. It's guaranteed to be balanced, so you get O(lg n) time insertions and delete-the-minimum operations, with low constant factors. Nice! But how do you make it concurrent? You can put a lock on the whole thing and only let one thread use it at once, but that's slow. You could use fancy fine-grained locking, but there will still be inter-thread memory conflicts arising from the heapify operations you need to maintain the heap invariant. There has been some work on this, and they've come up with some decent ideas, but it still has scaling problems. Now look at skip lists. It's a randomized sorted list data structure, and it claims to be, as you put it, probably pretty balanced. Various threads can insert concurrently without breaking that "probably pretty balanced" property. The memory read- and write-sets are very local, and it's possible to do all this with lock-free synchronization. The end result is a priority queue data structure that scales to hundreds of cores. And the code doesn't fry your brain, which is a plus. There's a pretty neat paper about it here: http://www-cs-students.stanford.edu/~itayl/ipdps.pdf http://www-cs-students.stanford.edu/~itayl/ipdps.pdf By the way, if you happen to be using a processor with hardware transactional memory support (you aren't, yet), then this code becomes even easier to write, as you don't have to worry about how to do lock-free synchronization. I almost felt cheated by how simple it was.
  - jamii 16y ago
    The general lesson is that randomized algorithms often remove the need for synchronization between concurrent processes. For example, choosing ids at random from a large space rather than coordinating to choose unique ids.
  - scott_s 16y ago
    What and where are you working that you have access to a processor with hardware transactional memory support?
xtacy 16y ago
An interesting application of skip lists: http://www.skorks.com/2010/03/faster-list-intersection-using-skip-pointers/ http://www.skorks.com/2010/03/faster-list-intersection-using... But I can't see why the same cannot be done using trees. :-/

panic 16y ago

Nobody mentioned the unrolled linked list, a simple, useful, and often-overlooked data structure. http://en.wikipedia.org/wiki/Unrolled_linked_list http://en.wikipedia.org/wiki/Unrolled_linked_list 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.

sjf 16y ago
Hah, I never knew there was a name for it, thanks.
jules 16y ago
An interesting variation on this is the VList, which works the same way except the inner arrays have variable size. This gives you an asymptotic rather than constant speedup for many operations. http://en.wikipedia.org/wiki/VList http://en.wikipedia.org/wiki/VList
Retric 16y ago
Yep, unrolled liked lists often work great for sparse 2D data structures especially when you get a lot of clustering around small areas. (think spreadsheets)
pjscott 16y ago
At one point, Python tried to move to something similar for their standard list data structure: http://www.python.org/dev/peps/pep-3128/ http://www.python.org/dev/peps/pep-3128/ The BList is similar to a B+Tree. It was meant to act like an array for small lists, but to make operations like append, concatenation, and slicing faster. It was a pretty cool combination of arrays (for memory compactness and good cache performance and small constant factors) with trees, for the asymptotic improvements they can bring. Sadly, it didn't take off, as it would have broken backward compatibility with extension modules.
- _delirium 16y ago

seldo 16y ago

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

araneae 16y ago
How much effort do you put into understanding them? As with everything, the more complicated something is (or the further away things are from what you're familiar with) the more you have to put into it. If you're interested in understanding them, I recommend finding another source for the explanation, like Wikipedia. The ones on stackoverflow can be a little short for an adequate explanation. Also, there's a limit to how much you can understand by just reading something. Try drawing it out. And in the end, I'm not sure how much understanding this stuff relates to your need for developers, depending on what you're doing. Most web programming involves getting cogs to fit with other cogs, not advanced algorithms. Obscure data structures are generally obscure for a reason; they're more an intellectual curiosity than anything else ^-^.
- jacquesm 16y ago
  > Obscure data structures are generally obscure for a reason; they're more an intellectual curiosity than anything else ^-^. I don't think that's necessarily true, the problem is that there are so many of them. Consider woodworking. A good woodworker has an absolutely enormous array of tools, and all a woodworker does, if you think about it with the mindset of a non-woodworker is remove bits of wood from other bits of wood and put them back together again. Algorithms are the tools in the toolbox of the programmer, all we do is transform series of bits in to other series of bits. But the number of algorithms is huge compared to the number of tools a woodworker uses, and it is impossible to remember all of them, to pick the one that is 'most appropriate' for the problem at hand. So we may end up using a sub-optimal solution quite a few times when one of the 'obscure' algorithms would have been more appropriate, just because computers are for the most part fast enough to cover for the inefficiencies.
  - seldo 16y ago
    To extend your analogy though, obscure algorithms could be like the techniques that allow master craftsmen to build beautiful, solid furniture using only careful joins and maybe light wood glue. On the other hand, what most people want is something quickly and cheaply assembled from standard parts from IKEA.

ljlolel 16y ago

By far the coolest data structure is the soft heap (http://www.link.cs.cmu.edu/15859-f07/papers/chazelle-soft-heap.pdf http://www.link.cs.cmu.edu/15859-f07/papers/chazelle-soft-he...). From wikipedia: http://en.wikipedia.org/wiki/Soft_heap http://en.wikipedia.org/wiki/Soft_heap 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:

igravious 16y ago
Off-topic but meh. The guy is a frighteningly funny and shrewd to boot. See any of his posts at A Tiny Revolution http://www.tinyrevolution.com/mt/ http://www.tinyrevolution.com/mt/ Oh a thanks for the heads-up on this data structure ljlolel.

argv_empty 16y ago

An earlier HN item discussed an interesting one (http://news.ycombinator.com/item?id=1156628 http://news.ycombinator.com/item?id=1156628)

RodgerTheGreat 16y ago

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

jacquesm 16y ago

it's hard to qualify 'lesser known', I'm not sure if red-black trees qualify, but they're certainly cool: http://en.wikipedia.org/wiki/Red-black_tree http://en.wikipedia.org/wiki/Red-black_tree

pjscott 16y ago
I like relaxed balanced red-black trees. In those, you're allowed to violate the balancing conditions; you can go back and fix the violations later. This is useful if you want to use them concurrently. The balancing transformations tend to cause lots of contention between threads, so deferring that rebalancing for a later, clean-up thread can really help with scalability.
- jacquesm 16y ago
  I only learned about this fairly recently: http://www.itl.nist.gov/div897/sqg/dads/ http://www.itl.nist.gov/div897/sqg/dads/ And I feel pretty stupid for not having realized earlier that something like that almost has to exist.
  - pjscott 16y ago
    Heh; it hit me that way, too. It seems obvious in retrospect. I found that this page has a nice mini-introduction: http://www.imada.sdu.dk/~kslarsen/RelBal/ http://www.imada.sdu.dk/~kslarsen/RelBal/ If requests that use a red-black tree tend to come in bursts, then you can probably get speedups by deferring rebalancing for idle periods, even single-threaded. That's pretty darn cool. I would like to see some programming language runtime that watched rb-tree access patterns and decided if this would be a good idea at runtime.
scott_s 16y ago
I was under the impression that most balanced binary trees were red-black trees. I know most C++ STL std::map implementations are red-black trees, as is Java's TreeMap.

Darmani 16y ago

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. 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.

jules 16y ago
It's not all good however. Try representing all valid Sudokus with a ZDD

sjs 16y ago

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". "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." -- http://en.wikipedia.org/wiki/Kd-tree http://en.wikipedia.org/wiki/Kd-tree

cloudkj 16y ago
I second kd-trees. I also only recently learned them, and at first encounter thought that they are in concept similar to binary space partitions used in computer graphics. Nearest neighbor search can be implemented using a pretty simple two-dimensional kd-tree. Useful for things like finding the n closest neighboring points for a given point on a plane (used for mapping applications, etc.)

budwin 16y ago

happy to see disjoint sets in there

ulvund 16y ago

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

jperras 16y ago

The Markov Chain: http://www.itl.nist.gov/div897/sqg/dads/HTML/markovchain.html http://www.itl.nist.gov/div897/sqg/dads/HTML/markovchain.htm...