News for hackers. Stuff that matters.
Re:Topics in Advanced Data Structures [pdf] by lichtenberger on Monday April 29, 2019 @02:25PM (#19781094)
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?
Re:Topics in Advanced Data Structures [pdf] by htiek on Monday April 29, 2019 @02:30PM (#19781145)
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.
Re:Topics in Advanced Data Structures [pdf] by lichtenberger on Monday April 29, 2019 @02:43PM (#19781296)
Thanks, great use case and I have to say I have to read about genomics... :-)
Re:Topics in Advanced Data Structures [pdf] by atlassubbed on Monday April 29, 2019 @06:43PM (#19783316)
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.
Re:Topics in Advanced Data Structures [pdf] by SnowflakeOnIce on Monday April 29, 2019 @08:01PM (#19783804)
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.

Re:Topics in Advanced Data Structures [pdf] by danharaj on Monday April 29, 2019 @02:32PM (#19781175)
I've seen it used in blockchain analysis and calculating the base for a three way merge operation.
Re:Topics in Advanced Data Structures [pdf] by lichtenberger on Monday April 29, 2019 @02:45PM (#19781316)
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 :)

Re:Topics in Advanced Data Structures [pdf] by ska on Monday April 29, 2019 @02:48PM (#19781347)
Perhaps worth starting with Merkel trees before digging into blockchain implementations.
Re:Topics in Advanced Data Structures [pdf] by lichtenberger on Monday April 29, 2019 @04:24PM (#19782270)
I'm familiar with merkle trees :-)
Re:Topics in Advanced Data Structures [pdf] by lichtenberger on Monday April 29, 2019 @04:25PM (#19782278)
Thanks for the suggestion/tip :-)