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

151–160 of 772 posts

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

#151

Post by School-Cotton »

mountainreason wrote: post #149
School-Cotton wrote: post #143

Earlier quoted context omitted.

Do we mean different things by "merge join" and "nested loop join" ? For me "merge join" is O(n) (but requires the data to be sorted by key) whereas "nested loop join" is O(n^2).

Wouldn't you at least be looking at nlog(n) for the sort in the merge join?

Yes, if the data is not already sorted. Thus it's O(n) for already sorted data and O(n log(n) + n) -- which simplifies to O(n log(n)) -- for arbitrary data.

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

#152

Post by epelesis »

BW Trees are pretty neat [1][2]. Typically BTrees in database engines need latches to prevent concurrent writes messing up the tree but BW Trees conveniently sidestep that requirement by appending all node updates to a linked list (called a Delta Chain), and having each reader apply the delta of updates by traversing the linked list until it hits the final node in the list. Periodically, these linked lists are compacted back into single nodes.

If you like these kinds of data structures, the Database Internals [3] book has a good introduction and explanation of a handful of BTree optimizations like this.

1: https://www.microsoft.com/en-us/research/wp-content/uploads/...

2: https://www.cs.cmu.edu/~huanche1/publications/open_bwtree.pd...

3: https://www.databass.dev/

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

#154

Post by champtar »

loxias wrote: post #64

(Fantastic post idea OP. One of the best I've ever seen :D) Related to bloom filters, xor filters are faster and more memory efficient, but immutable. HyperLogLog is an efficient way to estimate cardinality. Coolest thing I've learned recently was Y-fast trie. If your dataset M is bounded integers (say, the set of all 128 bit numbers), you get membership, predecessor, or successor queries in log log time, not log, li…

A fantastic thing about HyperLogLog is that it can be merged, so you can split your data between multiple server, precompute HLL for all IPs every minute, and then ask "how many unique IPs was there yesterday".

Discovered HLL because it's used in ClickHouse, which employ a ton of cool but obscure data structure.

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

#155

Post by hgs3 »

kaylynb wrote: post #44

Sparse sets. They're often used in Entity Component System architectures since you have O(1) add/remove/find, & O(n) iteration. Iterations are also packed, which is a bonus for cache efficiency. Can be difficult to implement well, but the concept is simple and a neat example of a useful specialty data structure. Take a look at https://github.com/skypjack/entt

You can apply the same idea to hash tables: Store hashes and dense-array indices in your sparse array, during lookup use robin hood hashing to cache efficiently probe the sparse array for a matching hash value, and if a match is found use the dense-array indice to lookup the data in the packed/dense array. This approach is both cache efficient and space efficient as the dense array can grow independently of the sparse array.

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

#156

Post by jedimastert »

z3t4 wrote: post #76

A sorted list. It's often cheaper to sort the list after each change, then to search the whole list. Especially when you do collision detection in 3d... (maybe not so obscure, but at least underestimated) When I pair my socks I first place them in color order :)

I was reading up on C++'s standard library and found out that maps and sets are generally implemented as continually sorted lists

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

#157

Post by noman-land »

freen wrote: post #113

Fountain Codes: reconstruct data from random selection of packets. Was deeply patent encumbered until recently. https://en.m.wikipedia.org/wiki/Fountain_code

I searched this thread far and wide for fountain codes. Surprised they're so low on the list. I find them amazing. Aso, the name is really good. The fact that you can collect any random packets in any order invokes the idea of putting a cup under a fountain and letting it fill up with water. Love it.

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

#158

Post by TrackerFF »

winrid wrote: post #18

Structures good for Geospatial information like rtrees, quadtrees. https://en.m.wikipedia.org/wiki/R-tree Also concurrent data structures. https://youtu.be/jcqGSehrMGU

Yes, R-tree turned out to be a godsend when working with larger geospatial data and calculating intersections.
Post reply on HN