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

91–100 of 772 posts

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

#91

Post by dundarious »

Blahah wrote: post #85

1. Probabilistic filtering and matching: Since you mentioned bloom filters - other probabilistic data structures like count-min sketches (roughly, streaming bloom filters) are super useful. Approximate kmer methods like minhash and w-shingling use them in really cool ways. Rolling hash methods like Rabin chunking also work really nicely with probabilistic/streaming hash tables - splitting the data stream into chunks…

Funny you should mention bloom filters and that use case, I just re-read this post again this morning: https://blog.cloudflare.com/when-bloom-filters-dont-bloom/

Basically, it makes a similar point to https://news.ycombinator.com/item?id=32186837 — i.e., cache effects are not modeled in big O analysis, even though most problems that involve large amounts of data (so most problems) are memory bound rather than CPU bound. The blog post makes a good case for a very simple hash table as a better fit for this problem.

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

#92

Post by js2 »

andrenotgiant wrote: post #65

Can I describe a data queueing problem that I feel like there is a specific data (or queue) structure for, but that I don't know the name is? Let's say you are trying to "synchronize" a secondary data store with a primary data store. Changes in the primary data store are very "bursty", one row will not change for days, then it'll change 300 times in a minute. You are willing to trade a bit of latency (say 10 seconds)…

Sentry used Redis to buffer writes for a similar use case:

https://blog.sentry.io/2016/02/23/buffering-sql-writes-with-...

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

#93

Post by pjscott »

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

Note that re-sorting an array after making a constant number of changes can be done in O(n) and will usually be very fast in practice. Insertion sort will do it, as will Timsort and similar algorithms.

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

#94

Post by mamcx »

leeoniya wrote: post #81
mamcx wrote: post #7

I made https://github.com/mamcx/tree-flat as flattened stored tree in pre-order that allows for very fast iterations even for childs/parent queries. Is based on APL, so not that novel. I also like a lot the relational model, is not that much represented so I making a language on top of it: https://tablam.org .

https://en.m.wikipedia.org/wiki/Nested_set_model ?

Yeah, that one is good, but I bet is possible to encode trees efficiently as relations without indirections.

That is part of my look at `tree-flat` and I wanna base trees on that for my lang.

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

#96

Post by blueblob »

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…

Sounds a bit like radix sort?

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

#98

Post by pacaro »

zarzavat wrote: post #55

Spatial hashing. Say that you have data that is identified with points in 2D or 3D space. The standard way that CS students learn in school to represent this is via a quadtree or octree. However, these tree data structures tend to have a lot of "fluff" (needless allocations and pointer chasing) and need a lot of work to be made efficient. Spatial hashing is the stupidly simple solution of just rounding coordinates to…

TBH even quadkeys are a fun answer to OPs question, many people aren't aware of them.

Simple explanation:

If you have data with x y coordinates and you know the bounds.

To compute the quad key for a point:

1. The key starts as the empty string. (I've also seen it start with "Z" to handle points outside the bounds)

2. Divide the space into 4 quadrants

3. determine which quadrant the point falls in, append a letter (A-D depending on the quadrant) to the key

4. Repeat step 3 using the quadrant bounds (i.e. recursively smaller area) until you have desired accuracy

This can then be used to efficiently find points within rectangular bounds.

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

#99

Post by pjscott »

lizardactivist wrote: post #27

The Trie is pretty cool. I think it's a bit obscure because the memory use can grow quite fast.

That depends very much on how the trie is represented in memory. Something like a burst trie or HAT trie is usually very compact!

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

#100

Post by chrchang523 »

jhallenworld wrote: post #77

Some ones I've used recently: The "golden section search" to find a the minimum (or maximum) of a unimodal function. An actual real-world use case for the golden ratio. Exponentially Weighted Moving Average filters. Or how to have a moving average without saving any data points.. Some of my classic favorites: Skiplists: they are sorted trees, but the algorithms are low complexity which is nice. Boyer-Moore string sea…

Regarding the bit “compress” operation, this is supported in hardware (PEXT instruction) by Haswell and newer processors, though unfortunately most AMD processors have poor implementations. I’ve found it to be quite handy when implementing subsetting operations.
Post reply on HN