What are the lesser known but useful data structures?
stackoverflow.com
What are the lesser known but useful data structures?
1–10 of 82 posts
Re: What are the lesser known but useful data structures?
#2[deleted]
Re: What are the lesser known but useful data structures?
#3Bloom filters and count-min sketch are awesome.
http://en.wikipedia.org/wiki/Bloom_filter http://en.wikipedia.org/wiki/Count%E2%80%93min_sketch
Re: What are the lesser known but useful data structures?
#4Looking at these lists, I strongly suspect that people upvote based on whether they personally recognize the data structure.
It goes against the intent of the original question, but iIt's almost ideally designed to make you feel good--you get the rush of knowledge then nerd sniped as you head to wikipedia.
Re: What are the lesser known but useful data structures?
#5I use a Hierarchical Triangular Mesh for indexing gamma ray events from the universe. The data is partitioned in the database according to it's HTM id.
http://arxiv.org/pdf/cs/0701164.pdf
Currently I use this for indexing ~11 billion gamma ray events. Researchers typically supply a region in the sky, a search radius, and some cuts (energy, event quality, etc...)
Re: What are the lesser known but useful data structures?
#6There's a whole set of interesting data structures that are not very well known: succinct data structures[1]. The idea is simple: we want to store data in a compressed form, but also perform certain operations quickly without uncompressing.
These can be very useful for certain applications. The article on "Cramming 80,000 Words into a JavaScript File"[2] is a nice example. It shows you how you can store a compressed trie in memory but still use it. I also like this[3] series of blog posts leading up to wavelet trees.
These certainly count as obscure data structures, unlike many of the ones listed on SO. I had never even considered the idea of compressing data in memory like this, much less encountered actual examples of succinct data structures! I have to thank Edward Kmett for introducing me to the whole field.
These data structures are important not just because they're neat themselves, but because they got me to think a new way. In particular, I realized that using pointers all over the place--to represent things like trees--is not always efficient. Instead of parsing data, it might be better to store it as a blob of some sort with a binary index. Just starting to consider details like that is valuable all on its own.
[1]: http://en.wikipedia.org/wiki/Succinct_data_structure
[2]: http://stevehanov.ca/blog/index.php/?id=120
[3]: http://alexbowe.com/rrr/ and http://alexbowe.com/wavelet-trees/
Re: What are the lesser known but useful data structures?
#7I don't really consider tries and bloom filters all that poorly known. These commonly come up in interviews for fresh graduates at Google/Facebook. Zippers, skip lists, ropes, round-robin databases, etc. are more genuinely not known I think.
Re: What are the lesser known but useful data structures?
#8Looking at these lists, I strongly suspect that people upvote based on whether they personally recognize the data structure. It goes against the intent of the original question, but iIt's almost ideally designed to make you feel good--you get the rush of knowledge then nerd sniped as you head to wikipedia.
Lest people think this is useless negativity, the point is that you need to scroll down and look at the other pages to see the really interesting ones. :)
Re: What are the lesser known but useful data structures?
#9Extendible hashing is amazing in space utilization while retaining the performance of hashing.
Re: What are the lesser known but useful data structures?
#10> This question exists because it has historical significance, but it is not considered a good, on-topic question for this site, so please do not use it as evidence that you can ask similar questions here.
Yet it's one of the best questions on SO. Something's very wrong with SO if this isn't considered a good, on-topic question for a programming Q&A site.