Ask HN: What are some cool but obscure data structures you know about?

Re:Ask HN: What are some cool but obscure data structures yo... by anon291 on Thursday July 21, 2022 @07:31PM (#32186571)

Finger 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)

https://andrew.gibiansky.com/blog/haskell/finger-trees/

[ Parent | on HN ]

Re:Ask HN: What are some cool but obscure data structures yo... by scott_s on Thursday July 21, 2022 @10:25PM (#32187750)

You might enjoy a paper I’m a coauthor on which combines finger trees with B-trees to build a data structure for optimal updates to sliding windows: Optimal and General Out-of-Order Sliding-Window Aggregation, https://www.scott-a-s.com/files/vldb2019_fiba.pdf

Slides from the conference talk: https://www.scott-a-s.com/files/vldb2019_fiba_slides.pdf

[ Parent | on HN ]

Re:Ask HN: What are some cool but obscure data structures yo... by yellowflash on Thursday July 21, 2022 @11:19PM (#32188091)

Very interested in your idea. How does concurrent updates work with the augumented trees? I have been thinking about the same for a while something like CouchDB but segment aggregations (monoid) augumented so we can do interval queries over time too. But the only thing bothering is augumented trees are notorious of contention on concurrent updates. Do you have any ideas on merging back if we have multiple versions of augumented trees.

[ Parent | on HN ]

Re:Ask HN: What are some cool but obscure data structures yo... by pjscott on Thursday July 21, 2022 @09:27PM (#32187398)

You can do this with any tree, finger or otherwise, and the big-O stuff applies as long as the tree is within a constant factor of balanced. For some bizarre reason, though, the concept of caching a monoid in each node doesn’t seem to have spread to the standard libraries of most languages. It’s a pity, since that would be incredibly useful.

[ Parent | on HN ]

Re:Ask HN: What are some cool but obscure data structures yo... by endgame on Friday July 22, 2022 @02:09AM (#32189054)

Finger Trees Explained Anew is a great derivation of the data structure: https://www.youtube.com/watch?v=ip92VMpf_-A

[ Parent | on HN ]

Re:Ask HN: What are some cool but obscure data structures yo... by throwamon on Friday July 22, 2022 @12:47AM (#32188631)

If I'm not mistaken, Clojure's data structures are (or used to be) implemented using finger trees.

[ Parent | on HN ]

Re:Ask HN: What are some cool but obscure data structures yo... by JonChesterfield on Saturday July 23, 2022 @07:36AM (#32202384)

A variation on 32 wide Bagwell hashed tries last time I looked. Scala was too. Those are much more annoying to implement without garbage collection fwiw.

[ Parent | on HN ]

Re:Ask HN: What are some cool but obscure data structures yo... by jacamera on Thursday July 21, 2022 @08:03PM (#32186853)

Very interesting! Sounds similar to a segment tree: https://en.wikipedia.org/wiki/Segment_tree

[ Parent | on HN ]