Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

news.ycombinator.com

Post reply on HN
Print view View original

501–510 of 772 posts

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

#501

Post by arunk-s »

twic wrote: post #388
tresil wrote: post #275

Earlier quoted context omitted.

Big fan of HLL Apache foundation has a fantastic DataSketches library that includes HLL and many other powerful data analytics algorithms: https://datasketches.apache.org/ Lee Rhodes has done an excellent introduction to this library - explaining some of the use cases, advantages, and things to be aware of when using these techniques: https://www.youtube.com/watch?v=nO9pauS-mGQ

On sketches, there is a genre of structure for estimating histogram-like statistics (median, 99th centile, etc) in fixed space, which i really like. Two examples: t-digest https://github.com/tdunning/t-digest DDSketch https://github.com/DataDog/sketches-java

In the same spirit there is also Circllhist from Circonus. https://arxiv.org/abs/2001.06561

There was a good discussion on approaches to store histogram here: https://news.ycombinator.com/item?id=31379383

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

#502

Post by lscharen »

CDAWGs. Compressed Directed Acyclic Word Graphs.

They are like tries but share prefixes and suffixes of a word corpus, can be built in linear time, and since they are graphs, one can define an inner product between two CDAWGs and use them for kernel-based machine learning algorithms.

https://hal-upec-upem.archives-ouvertes.fr/hal-00620006/docu...

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

#503

Post by SahAssar »

https://en.wikipedia.org/wiki/Macaroons_(computer_science) are very interesting to me.

Think of it as a JWT that you can narrow down the authorizations for without needing to communicate with a server, so if you have read permissions to all your photos you can add a caveat saying `photoid=123456` and share it, and the recipient can only read the photo 123456. The caveats can be anything, including requiring third party authentication via third-party caveats. I've implemented systems with it being validated by a lua module in nginx which worked well, but the whole concept never took off.

I still think it seems like one of the most interesting authZ strategies around.

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

#505

Post by FridgeSeal »

remorses wrote: post #485

Struct of arrays (also called MultiArrayList in Zig), instead of storing big structs in an array you store each field in a separate array and if you need to fetch the full struct you reconstruct it from the arrays. The benefit is that the arrays items memory size is smaller and has no padding, it also increases cache locality.

Now I remember reading a blog post recently, about an Areta library (one of the rust ones maybe?) that were doing both: array-of-struct-of-array.

The idea was to split the main arrays up into “chunks” that were structs, themselves containing rows of data (still array oriented).

The idea was that you retain the cache/layout/performance benefits of SoA layout, except each chunk is already packaged up into lengths ready for pushing through SIMD. Quite a clever idea.

Found it: https://www.rustsim.org/blog/2020/03/23/simd-aosoa-in-nalgeb...

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

#506

Post by Gregam3 »

m12k wrote: post #495

The Bag. Also known as a Multiset. I can't believe it took me so many years to learn the name of the most basic data structure imaginable - it basically makes no promises whatsoever about the structure. Think of it like a Set that allows duplicates - you can put stuff in and take stuff out, just like a bag - what more could you want?

I love the Bag! It's so simple I use it constantly

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

#507

Post by Gregam3 »

chirau wrote: post #499
m12k wrote: post #495

The Bag. Also known as a Multiset. I can't believe it took me so many years to learn the name of the most basic data structure imaginable - it basically makes no promises whatsoever about the structure. Think of it like a Set that allows duplicates - you can put stuff in and take stuff out, just like a bag - what more could you want?

How is that any different from a list?

Hopefully this java can illustrate the point if you're not a Java lover

The bag essentially works like this Map>

But looks like this Bag

I use my own simple "BagSet" which works like this Map>

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

#508

Post by FridgeSeal »

Succinct data structures are one of my favourites.

The idea that we can very cleverly pack a collection of information into a much smaller form, but you can query the compressed form with good computational complexity, and without unpacking the data you need to read is amazing.

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

#509

Post by ignoramous »

mkirchner wrote: post #372
filoeleven wrote: post #198

HAMT: Hash Array Mapped Trie. This data structure makes efficient immutable data possible. You can update a list of a million items, and keep a reference to the original list, by changing 3 or 4 references and some bytes. This should replace copy-on-write for scripting languages. I really want to see it in a JS spec soon. There are libraries that can do it, but they add translation penalties and extra steps. I’d comp…

This. Roughly a year ago I got interested in efficient immutability for my write-from-scratch-in-C Lisp [0] and started to write a HAMT implementation in C [1], along with a (somewhat hacky, you have been warned) benchmarking suite [2]. The docs are only 70% done (in particular the "putting it all together" part is missing) but it has been a really interesting and enlightening journey so far and can only recommend em…

See also Matt Bierner's HAMT impl in JavaScript: https://blog.mattbierner.com/hash-array-mapped-tries-in-java...

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

#510

Post by FridgeSeal »

SahAssar wrote: post #503

https://en.wikipedia.org/wiki/Macaroons_(computer_science) are very interesting to me. Think of it as a JWT that you can narrow down the authorizations for without needing to communicate with a server, so if you have read permissions to all your photos you can add a caveat saying `photoid=123456` and share it, and the recipient can only read the photo 123456. The caveats can be anything, including requiring third par…

I’ve heard of these!

The fly.io blog has a really cool write-up about them.

Definitely an under appreciated concept.

IIUC, you can even validate the “sub issued” macaroons offline, provided you know the validity of one of its ancestors up the chain. Is this correct, or am I misunderstanding?

Post reply on HN