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

101–110 of 772 posts

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

#101

Post by loxias »

blueblob wrote: post #96
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?

AIUI Radix sort "kinda ish" related, yeah :) They both involve looking at your data at a 90 degree angle and slicing on bitplanes.

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

#102

Post by Loranubi »

I am trying to compile a list of data structures (and algorithms and other stuff) into a kind of knowledge base: https://github.com/Dobatymo/data-algos/blob/master/data-stru.... There are few cool and obscure data structures already. Please feel free to help extend it!

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

#104

Post by nicwolff »

The Aho-Corasick automaton [0]. You have a bunch of strings, and you want to know if and where they appear in a longer string. You build a search trie from the strings, but add links back from each node to the node representing the longest suffix of the string it represents that is also in the trie, so you can skip backtracking as you scan, yielding linear time complexity in O(length of string being searched + number of results found).

[0] https://en.wikipedia.org/wiki/Aho–Corasick_algorithm

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

#105

Post by trebcon »

vvanders wrote: post #42
jiggawatts wrote: post #25

Cache-Oblivious Data Structures: https://cs.au.dk/~gerth/MassiveData02/notes/demaine.pdf A vaguely related notion is that naive analysis of big-O complexity in typical CS texts ignores over the increasing latency/cost of data access as the data size grows. This can't be ignored, no matter how much we would like to hand-wave it away, because physics gets in the way. A way to think about it is that a CPU core is like a…

Realtime collision detection[1] has a fantastic chapter in this with some really good practical examples if I remember right. Great book, I used to refer to it as 3D "data structures" book which is very much in theme with this thread. [1] https://www.amazon.com/Real-Time-Collision-Detection-Interac...

The implicit grid data structure from there is a personal favorite of mine. I used it in a game once and it performed incredibly well for our use case.

It's a bit too complicated to totally summarize here, but it uses a bit per object in the scene. Then bit-wise operations are used to perform quick set operations on objects.

This data structure got me generally interested in algorithms that use bits for set operations. I found the Roaring Bitmap github page has a lot of useful information and references wrt this topic: https://github.com/RoaringBitmap/RoaringBitmap

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

#106

Post by pjscott »

dundarious wrote: post #91
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 bou…

If you’re willing to use moderately more memory, you can get much better cache locality using a blocked bloom filter. The basic idea is to use an array of bloom filters that each fit into a cache line, and use some bits of hash to determine which sub-filter each item goes into. Suddenly each lookup or insertion has at most one cache miss!

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

#107

Post by ffhhj »

Latent Dirichlet Allocation (LDA) structure:

"LDA represents documents as mixtures of topics that spit out words with certain probabilities."

"LDA assumes that each document in a corpus contains a mix of topics that are found throughout the entire corpus. The topic structure is hidden - we can only observe the documents and words, not the topics themselves. Because the structure is hidden (also known as latent), this method seeks to infer the topic structure given the known words and documents."

https://cfss.uchicago.edu/notes/topic-modeling/

I'm making a next-gen search engine.

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

#108

Post by vlmutolo »

dundarious wrote: post #91
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 bou…

That Cloudflare article is a little frustrating.

> While we could think of more sophisticated data structures like Cuckoo filter, maybe we can be simpler

Yes, standard Bloom filters fail for large filter sizes and/or very small false-positive rates. But we've known this for decades, and tons of other probabilistic filters have come out since then to address the problem. Cuckoo filters in particular are incredible.

Was there really no easy way to bring in an open-source Cuckoo filter implementation? They're not that complicated. Maybe I'm just used to modern languages having good package managers.

Plus the author's solution is basically the idea behind Cuckoo filters: "what if we just use a hash table, but allow for collisions?" Cuckoo hashing is just clever about guaranteeing O(1) worst-case lookup.

And for absolute dead-simple filters, a blocked Bloom filter is basically just as easy as a Bloom filter. It's like two or three more lines of code. It's just changing the indexing operation to be modulo some large "block" size. That said, I don't think they'd work too well in this case, since the author has a pretty small false-positive rate (0.000019), and in my experience small Bloom filters (which is what comprise blocked Bloom filters) don't handle small FP rates well.

But guess what excel at small FP rates… cuckoo filters.

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

#109

Post by jefftk »

NSMutableSet wrote: post #75
OJFord wrote: post #41

Earlier quoted context omitted.

The starting example was Bloom filters.

I'm not sure what the point of your post is. While bloom filters are heavily used in actual production code throughout the industry, it is very rare for anyone to need to code their own, or make changes to a prior legacy implementation. Not all educational programs will cover bloom filters, and for those that do, there's no guarantee that the students will retain the information, and be able to recall it. I don't kno…

I was with you until the last seven words ;)

Trees were a huge part of CS practice and education historically, but have been replaced by hash-based methods in many cases. For example, in C++ std::map is generally a tree, while in a more recent language the standard Map data structure will be a hashmap. My impression is that the instruction time devoted to Bloom filters (and other hash-based methods) vs trees has shifted towards the former over the last ~20y.

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

#110

Post by jhallenworld »

glouwbug wrote: post #36

Static arrays - when was the last time you used a static array?

I find I use fixed-sized arrays a lot on microcontrollers. You want to avoid the heap (for reliability) and you don't have a lot of RAM, so you must carefully size your fixed-size arrays.
Post reply on HN