19 ms·

Topics in Advanced Data Structures [pdf]

931 points by htiek 7y ago

pizza 7y ago
This is quite cool, thanks.
lichtenberger 7y ago
Hm, where else are Lowest Common Ancestors in tree-structures useful? Storing for instance ORDPATH/DeweyIDs allows to simply check for a common prefix (they are hierarchical node labels). I think maybe for locking in a storage system with multiple read/write transactions or to determine which of two given nodes is the firs one in preorder, which is useful for XQuery/XPath processing (to determine the so caslled document order). Can anyone think of other usages? Or for having hierarchical node labels in trees?
- htiek 7y ago
  You can use lowest common ancestor queries in conjunction with suffix trees to solve a lot of interesting string problems. For example, take two indices within a string, find their corresponding suffixes in the suffix tree, and then take their LCA. That gives you an internal node corresponding to the longest string that appears starting at both indices (this is called their "longest common extension.") You can use this as a subroutine in a bunch of genomics applications.
  - lichtenberger 7y ago
    Thanks, great use case and I have to say I have to read about genomics... :-)
    - deleted 7y ago
      [deleted]
- danharaj 7y ago
  I've seen it used in blockchain analysis and calculating the base for a three way merge operation.
  - lichtenberger 7y ago
    So much stuff you can learn in the computer science world. For me the blockchain still is more or less a black box, should read a book about this stuff, as it seems to be hyped everywhere ;-) Thanks :)
    - ska 7y ago
      Perhaps worth starting with Merkel trees before digging into blockchain implementations.
      - lichtenberger 7y ago
        I'm familiar with merkle trees :-)
      - lichtenberger 7y ago
        Thanks for the suggestion/tip :-)
- atlassubbed 7y ago
  Error-boundaries in VDOM frameworks. If you have an asynchronous diff cycle, you might get multiple errors from more than one node in a single diff cycle. One option is to bubble up errors to the nearest LCA that is an error-boundary. In general if you have marked two nodes in a tree and need to modify the smallest subtree that contains those nodes, then you will probably need to know the LCA.
- SnowflakeOnIce 7y ago
  Lowest Common Ancestor shows up in graph theory, particularly to help compute dominator trees or dominator frontiers. These problems arise in compilers that convert programs into static single assignment (SSA) form.
mountainofdeath 7y ago
Great! More fodder for interview questions /s.
- twoquestions 7y ago
  That's probably it, any use of these algorithms in business software would need to be justified for the increased training your fresh-out-of-school replacement would need to maintain this.
lame88 7y ago
Does anyone in their work find that they are able to employ data structures like this, and if so, what do you work on? I've almost always had to delegate all my state to a database using default indexes, etc., which is productive, yet a little disappointing, because I'm always applying my brain power instead toward more mundane tasks.
- oplav 7y ago
  It's not as interesting as some of the structures in the PDF, but we are working on a problem where we have lots of timestamped data and need to quickly and frequently access the nearest data point from a given input timestamp. We ended up using a tree-like structure but that said, we ended up using whatever tree-like structure was available in the language.
- vsef 7y ago
  Work in speech recognition, from this list use lots of advanced automata algorithms, bloomier filters, interesting types of hashing, fancy priority queues.
- sempron64 7y ago
  When working on a high volume web application I found data sketches (specifically the count-min sketch) very useful for finding and logging unique query patterns (Check if we've seen it before, how often have we seen it, if it's new, log it). Using a sketch bounded how much memory we used and eliminated database trips. In theory a hashmap data structure might have worked as well, but its size is unbounded given too many unique queries, while all we needed was an estimate. Probabilistic data structures like bloom filters and sketches are really useful for gathering statistics on data sets that are too large to manage or would have a negative performance impact by having an extra database trip. So something to do with internal application diagnostics/debugging/logging is a great low-risk place to use these sorts of algorithms even when it makes sense to keep all business logic in the database.
- deleted 7y ago
  [deleted]
- robmaister 7y ago
jhayward 7y ago
I was going to roll my eyes about stuff no one will ever hear of, much less use in their day job, but there are some really relevant structures here. Finger trees, cache-oblivious structures, R-trees, etc., just to name a couple from a random page or two. The "why they're worth studying" summaries are gold. Thanks!
- debatem1 7y ago
  FM indices as well.
- jwr 7y ago
  > much less use in their day job Yes, some are indeed very relevant. In one of my previous businesses, we built a search engine where we used DAWGs (Directed Acyclic Word Graphs) [I didn't do this part]. And they worked really, really well, in fact they work well to this day.
  - nathell 7y ago
    Good to hear they do. :)
- bhaavan 7y ago
  A doctor has to mostly always treat common cold, and influenza. But that's no excuse for her / him to not know the purpose of the left pulmonary vein. The more basics they know, the better doctors they are. Sorry if this analogy is a bit extreme, but I want to make a point.
  - jhayward 7y ago
    I think a more apt analogy would be if you would disqualify doctors who don't know the nucleotide sequence of the genes that code for the cytochrome p450 enzyme process from treating your cold or flu. The left pulmonary veins are gross anatomy, akin to knowing what an 'if' statement is. Knowing the current state of the art in determining a minimum complexity for an operation on an obscure tree implementation is deep domain knowledge used by only a few specialists.
beeforpork 7y ago
The list is great, but unfortunately has no pointers to documentation. I find nothing online for some of the topics. Where can I find the description and discussion of 'ravel trees'?
- nestorD 7y ago
  They also caught my eyes. I finally found a paper here (the correct denomination seems to be RAVL tree) : http://sidsen.azurewebsites.net/papers/ravl-trees-journal.pdf http://sidsen.azurewebsites.net/papers/ravl-trees-journal.pd...
  - beeforpork 7y ago
    Super, thanks for being better at searching! (The name makes more sense this way.) :-)
- deleted 7y ago
  [deleted]
amelius 7y ago
> Traditional data structures assume a single-threaded execution model and break if multiple operations canbe performed at once. (Just imagine how awful it would be if you tried to access a splay tree with multiplethreads.) Can you design data structures that work safely in a parallel model – or, better yet, take maxi-mum advantage of parallelism? In many cases, the answer is yes, but the data structures look nothing liketheir single-threaded counterparts. Makes me wonder which data structures have "parallel" versions besides the two mentioned.
- thekdude 7y ago
  The Art of Multiprocessor Programming by Herlihy and Shavit have many examples, including stacks, queues, skip lists, and hash tables. There's plenty of papers out there too that have parallel implementations of vectors, various tree structures and more.
- teej 7y ago
  Check out CRDTs - https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type https://en.wikipedia.org/wiki/Conflict-free_replicated_data_...
- dominotw 7y ago
  would all of scala's default( immutable) datastructures fit the bill?
  - dominotw 7y ago
    I was just curious. Not sure why this is downvoted.
maimeowmeow 7y ago
Please provide the solutions in git repo. Thanks.
- inetsee 7y ago
  Paraphrasing (almost every) math book: "Solutions are left as an exercise for the reader."
- gdy 7y ago
  Sure, but it will be quite expensive for you.
winrid 7y ago
This is awesome, thank you! Used nested R-Trees in a personal project recently (sharded in memory spacial db for a game) which is not something I thought I'd ever have to do.
Insanity 7y ago
The material seems to be for this course: http://web.stanford.edu/class/cs166/ http://web.stanford.edu/class/cs166/ There are more slides and info on that site :)
- copperx 7y ago
  It's a pity there are no video lectures. Are there lectures out there for a similar algorithms class?
  - reubenmorais 7y ago
    MIT 6.851 Advanced Data Structures, Spring 2012: https://www.youtube.com/playlist?list=PLUl4u3cNGP61hsJNdULdudlRL493b-XZf https://www.youtube.com/playlist?list=PLUl4u3cNGP61hsJNdULdu...
    - jbn 7y ago
      I took that class that year, one of the best classes I ever took. A ton of work, too.
criddell 7y ago
What font are they using? I find it very unpleasant to read on a 4k screen set to 125% scale. Or maybe it's Firefox.
- criddell 7y ago
  I loaded the page on Chrome and the text is definitely heavier (and more readable) but also less sharp.
bondant 7y ago
Does anyone know books which explore in depth recent development in advanced data structure (or just not well known advanced data structure) ?
carlb2312 7y ago
I like it
cryptokernel 7y ago
awesome topics. just leaving this here: https://coincircle.com/l/50VVxbObg3 https://coincircle.com/l/50VVxbObg3
hasahmed 7y ago
Where can I learn more about ravel trees?
- sus_007 7y ago
  From one of the comments on this thread. http://sidsen.azurewebsites.net/papers/ravl-trees-journal.pdf http://sidsen.azurewebsites.net/papers/ravl-trees-journal.pd...
bogdanoff_2 7y ago
This kind of stuff fascinates me. General software engineering seems comparatively boring. I was considering going back to university to do a phd in cs and this is making me realize that research in algorithms/data structure would actually be viable (still lots of stuff to discover). Does anyone here know what it is like doing research in these areas? Any general advice?
- xtracto 7y ago
  I've got a PhD in CS, and these structures fascinate me as well. The Bloomier Filter reads amazing. Unfortunately, day to day job has almost nothing to do with these algorithms, but mainly software architecture and maintainability. I think the majority of these algorithms are not really something you will find implementing in day to day work. And at most I can see myself using a library with one of those. Even if you do research, it will have to be very focused on data structures and algorithms to really get deep into some of these. Still, very enjoyable.
  - bhaak 7y ago
    > I think the majority of these algorithms are not really something you will find implementing in day to day work. And at most I can see myself using a library with one of those. That's true but if you don't know what's possible, it's likely that you don't even look for it or stumble over it randomly. So you should know about them, even if you never implement them. You wouldn't need to know about them in that detail for that but it's just plain fun to learn stuff like this. :-)
  - sterlind 7y ago
    Just today I finished implementing radix heaps in C# to optimize some of my Dijkstras.. When I googled I saw zero implementations in C#, so I may be the first to write it. It worked well, giving me 3x speedup in practice over DAry heap and very low GC pressure, fortunate as my process was exceeding 256GB ram. Rolling your own data structures is pretty vital if you're working on algorithms.
sidcool 7y ago
I love learning Algorithms and Data Structures. The issue is that I don't get to use these frequently, not even basic DS. Most of what I need exists in the language or some framework, and if I am to implement it from scratch, I am sure I will do worse. The only time I really use this knowledge is during interviews.
- collyw 7y ago
  I (did) feel excatly the same. Now after working for 17 years I realize that I barely ever use this stuff, and when asked this stuff in an interview I do a lot worse than I did straight out of university. I am however a lot better software engineer than I was then.
vaibhavsagar 7y ago
My favourite somewhat obscure data structure that I didn't see on the list: Hash Array Mapped Tries.
panbabybaby 7y ago
nice sharing !!
collinmanderson 7y ago
I'm surprised no one mentioned the "Crazy Good Chocolate Pop Tarts" algorithm. That one took my by surprise :) https://www.researchgate.net/publication/51952511_De-amortizing_Binary_Search_Trees https://www.researchgate.net/publication/51952511_De-amortiz... Hilarious

931 points by htiek 7y ago

This is quite cool, thanks.

Hm, where else are Lowest Common Ancestors in tree-structures useful? Storing for instance ORDPATH/DeweyIDs allows to simply check for a common prefix (they are hierarchical node labels). I think maybe for locking in a storage system with multiple read/write transactions or to determine which of two given nodes is the firs one in preorder, which is useful for XQuery/XPath processing (to determine the so caslled document order). Can anyone think of other usages? Or for having hierarchical node labels in trees?

htiek 7y ago
You can use lowest common ancestor queries in conjunction with suffix trees to solve a lot of interesting string problems. For example, take two indices within a string, find their corresponding suffixes in the suffix tree, and then take their LCA. That gives you an internal node corresponding to the longest string that appears starting at both indices (this is called their "longest common extension.") You can use this as a subroutine in a bunch of genomics applications.
- lichtenberger 7y ago
  Thanks, great use case and I have to say I have to read about genomics... :-)
  - deleted 7y ago
    [deleted]
danharaj 7y ago
I've seen it used in blockchain analysis and calculating the base for a three way merge operation.
- lichtenberger 7y ago
  So much stuff you can learn in the computer science world. For me the blockchain still is more or less a black box, should read a book about this stuff, as it seems to be hyped everywhere ;-) Thanks :)
  - ska 7y ago
    Perhaps worth starting with Merkel trees before digging into blockchain implementations.
    - lichtenberger 7y ago
      I'm familiar with merkle trees :-)
    - lichtenberger 7y ago
      Thanks for the suggestion/tip :-)
atlassubbed 7y ago
Error-boundaries in VDOM frameworks. If you have an asynchronous diff cycle, you might get multiple errors from more than one node in a single diff cycle. One option is to bubble up errors to the nearest LCA that is an error-boundary. In general if you have marked two nodes in a tree and need to modify the smallest subtree that contains those nodes, then you will probably need to know the LCA.
SnowflakeOnIce 7y ago
Lowest Common Ancestor shows up in graph theory, particularly to help compute dominator trees or dominator frontiers. These problems arise in compilers that convert programs into static single assignment (SSA) form.

mountainofdeath 7y ago

Great! More fodder for interview questions /s.

twoquestions 7y ago
That's probably it, any use of these algorithms in business software would need to be justified for the increased training your fresh-out-of-school replacement would need to maintain this.

lame88 7y ago

Does anyone in their work find that they are able to employ data structures like this, and if so, what do you work on? I've almost always had to delegate all my state to a database using default indexes, etc., which is productive, yet a little disappointing, because I'm always applying my brain power instead toward more mundane tasks.

oplav 7y ago
It's not as interesting as some of the structures in the PDF, but we are working on a problem where we have lots of timestamped data and need to quickly and frequently access the nearest data point from a given input timestamp. We ended up using a tree-like structure but that said, we ended up using whatever tree-like structure was available in the language.
vsef 7y ago
Work in speech recognition, from this list use lots of advanced automata algorithms, bloomier filters, interesting types of hashing, fancy priority queues.
sempron64 7y ago
When working on a high volume web application I found data sketches (specifically the count-min sketch) very useful for finding and logging unique query patterns (Check if we've seen it before, how often have we seen it, if it's new, log it). Using a sketch bounded how much memory we used and eliminated database trips. In theory a hashmap data structure might have worked as well, but its size is unbounded given too many unique queries, while all we needed was an estimate. Probabilistic data structures like bloom filters and sketches are really useful for gathering statistics on data sets that are too large to manage or would have a negative performance impact by having an extra database trip. So something to do with internal application diagnostics/debugging/logging is a great low-risk place to use these sorts of algorithms even when it makes sense to keep all business logic in the database.
deleted 7y ago
[deleted]
robmaister 7y ago

jhayward 7y ago

I was going to roll my eyes about stuff no one will ever hear of, much less use in their day job, but there are some really relevant structures here. Finger trees, cache-oblivious structures, R-trees, etc., just to name a couple from a random page or two. The "why they're worth studying" summaries are gold. Thanks!

debatem1 7y ago
FM indices as well.
jwr 7y ago
> much less use in their day job Yes, some are indeed very relevant. In one of my previous businesses, we built a search engine where we used DAWGs (Directed Acyclic Word Graphs) [I didn't do this part]. And they worked really, really well, in fact they work well to this day.
- nathell 7y ago
  Good to hear they do. :)
bhaavan 7y ago
A doctor has to mostly always treat common cold, and influenza. But that's no excuse for her / him to not know the purpose of the left pulmonary vein. The more basics they know, the better doctors they are. Sorry if this analogy is a bit extreme, but I want to make a point.
- jhayward 7y ago
  I think a more apt analogy would be if you would disqualify doctors who don't know the nucleotide sequence of the genes that code for the cytochrome p450 enzyme process from treating your cold or flu. The left pulmonary veins are gross anatomy, akin to knowing what an 'if' statement is. Knowing the current state of the art in determining a minimum complexity for an operation on an obscure tree implementation is deep domain knowledge used by only a few specialists.

beeforpork 7y ago

The list is great, but unfortunately has no pointers to documentation. I find nothing online for some of the topics. Where can I find the description and discussion of 'ravel trees'?

nestorD 7y ago
They also caught my eyes. I finally found a paper here (the correct denomination seems to be RAVL tree) : http://sidsen.azurewebsites.net/papers/ravl-trees-journal.pdf http://sidsen.azurewebsites.net/papers/ravl-trees-journal.pd...
- beeforpork 7y ago
  Super, thanks for being better at searching! (The name makes more sense this way.) :-)
deleted 7y ago
[deleted]

amelius 7y ago

> Traditional data structures assume a single-threaded execution model and break if multiple operations canbe performed at once. (Just imagine how awful it would be if you tried to access a splay tree with multiplethreads.) Can you design data structures that work safely in a parallel model – or, better yet, take maxi-mum advantage of parallelism? In many cases, the answer is yes, but the data structures look nothing liketheir single-threaded counterparts. Makes me wonder which data structures have "parallel" versions besides the two mentioned.

thekdude 7y ago
The Art of Multiprocessor Programming by Herlihy and Shavit have many examples, including stacks, queues, skip lists, and hash tables. There's plenty of papers out there too that have parallel implementations of vectors, various tree structures and more.
teej 7y ago
Check out CRDTs - https://en.wikipedia.org/wiki/Conflict-free_replicated_data_type https://en.wikipedia.org/wiki/Conflict-free_replicated_data_...
dominotw 7y ago
would all of scala's default( immutable) datastructures fit the bill?
- dominotw 7y ago
  I was just curious. Not sure why this is downvoted.

maimeowmeow 7y ago

Please provide the solutions in git repo. Thanks.

inetsee 7y ago
Paraphrasing (almost every) math book: "Solutions are left as an exercise for the reader."
gdy 7y ago
Sure, but it will be quite expensive for you.

winrid 7y ago

This is awesome, thank you! Used nested R-Trees in a personal project recently (sharded in memory spacial db for a game) which is not something I thought I'd ever have to do.

Insanity 7y ago

The material seems to be for this course: http://web.stanford.edu/class/cs166/ http://web.stanford.edu/class/cs166/ There are more slides and info on that site :)

copperx 7y ago
It's a pity there are no video lectures. Are there lectures out there for a similar algorithms class?
- reubenmorais 7y ago
  MIT 6.851 Advanced Data Structures, Spring 2012: https://www.youtube.com/playlist?list=PLUl4u3cNGP61hsJNdULdudlRL493b-XZf https://www.youtube.com/playlist?list=PLUl4u3cNGP61hsJNdULdu...
  - jbn 7y ago
    I took that class that year, one of the best classes I ever took. A ton of work, too.

criddell 7y ago

What font are they using? I find it very unpleasant to read on a 4k screen set to 125% scale. Or maybe it's Firefox.

criddell 7y ago
I loaded the page on Chrome and the text is definitely heavier (and more readable) but also less sharp.

bondant 7y ago

Does anyone know books which explore in depth recent development in advanced data structure (or just not well known advanced data structure) ?

carlb2312 7y ago

I like it

cryptokernel 7y ago

awesome topics. just leaving this here: https://coincircle.com/l/50VVxbObg3 https://coincircle.com/l/50VVxbObg3

hasahmed 7y ago

Where can I learn more about ravel trees?

sus_007 7y ago
From one of the comments on this thread. http://sidsen.azurewebsites.net/papers/ravl-trees-journal.pdf http://sidsen.azurewebsites.net/papers/ravl-trees-journal.pd...

bogdanoff_2 7y ago

This kind of stuff fascinates me. General software engineering seems comparatively boring. I was considering going back to university to do a phd in cs and this is making me realize that research in algorithms/data structure would actually be viable (still lots of stuff to discover). Does anyone here know what it is like doing research in these areas? Any general advice?

xtracto 7y ago
I've got a PhD in CS, and these structures fascinate me as well. The Bloomier Filter reads amazing. Unfortunately, day to day job has almost nothing to do with these algorithms, but mainly software architecture and maintainability. I think the majority of these algorithms are not really something you will find implementing in day to day work. And at most I can see myself using a library with one of those. Even if you do research, it will have to be very focused on data structures and algorithms to really get deep into some of these. Still, very enjoyable.
- bhaak 7y ago
  > I think the majority of these algorithms are not really something you will find implementing in day to day work. And at most I can see myself using a library with one of those. That's true but if you don't know what's possible, it's likely that you don't even look for it or stumble over it randomly. So you should know about them, even if you never implement them. You wouldn't need to know about them in that detail for that but it's just plain fun to learn stuff like this. :-)
- sterlind 7y ago
  Just today I finished implementing radix heaps in C# to optimize some of my Dijkstras.. When I googled I saw zero implementations in C#, so I may be the first to write it. It worked well, giving me 3x speedup in practice over DAry heap and very low GC pressure, fortunate as my process was exceeding 256GB ram. Rolling your own data structures is pretty vital if you're working on algorithms.

sidcool 7y ago

I love learning Algorithms and Data Structures. The issue is that I don't get to use these frequently, not even basic DS. Most of what I need exists in the language or some framework, and if I am to implement it from scratch, I am sure I will do worse. The only time I really use this knowledge is during interviews.

collyw 7y ago
I (did) feel excatly the same. Now after working for 17 years I realize that I barely ever use this stuff, and when asked this stuff in an interview I do a lot worse than I did straight out of university. I am however a lot better software engineer than I was then.

vaibhavsagar 7y ago

My favourite somewhat obscure data structure that I didn't see on the list: Hash Array Mapped Tries.

panbabybaby 7y ago

nice sharing !!

collinmanderson 7y ago

I'm surprised no one mentioned the "Crazy Good Chocolate Pop Tarts" algorithm. That one took my by surprise :) https://www.researchgate.net/publication/51952511_De-amortizing_Binary_Search_Trees https://www.researchgate.net/publication/51952511_De-amortiz... Hilarious