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

131–140 of 772 posts

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

#131

Post by jiggawatts »

itamarst wrote: post #80
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…

Does anyone actually use cache-oblivious data structure in practice? Not, like, "yes I know there's a cache I will write a datastructure for that", that's common, but specifically cache-oblivious data structures? People mention them a lot but I've never heard anyone say they actually used them.

To an extent, the B-Tree data structure (and its variants) are cache oblivious. They smoothly improve in performance with more and more cache memory, and can scale down to just megabytes of cache over terabytes of disk.

The issue is that the last tree level tends to break this model because with some caching models it is "all or nothing" and is the biggest chunk of the data by far.

There are workarounds which make it more truly cache oblivious. How often this is used in production software? Who knows...

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

#132

Post by bmitc »

sgtnoodle wrote: post #45
bmitc wrote: post #40

Earlier quoted context omitted.

Do you have a link to the white paper you found?

This doesn't look like I remember, but this sounds right. https://lmax-exchange.github.io/disruptor/disruptor.html#_de... The basic idea is that you maintain two atomically incremented counters. You increment one to allocate some buffer space to write your message into, and you increment the other once the message is written in. There's some tricky details to get right when multiple producers have messages staged up…

Thank you!

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

#133

Post by yellowflash »

scott_s wrote: post #115
anon291 wrote: post #12

Finger trees allow you to do amazing things. In essence they let you build an index, or multiple indices, for your dataset and then store them in a single structure. When I go from Haskell back to imperative land I find myself greatly missing this ability. Sure I can make multiple hashmaps or trees or whatever but being able to stuff it all in one data structure is amazing. One structure I built with them that is muc…

You might enjoy a paper I’m a coauthor on which combines finger trees with B-trees to build a data structure for optimal updates to sliding windows: Optimal and General Out-of-Order Sliding-Window Aggregation, https://www.scott-a-s.com/files/vldb2019_fiba.pdf Slides from the conference talk: https://www.scott-a-s.com/files/vldb2019_fiba_slides.pdf

Very interested in your idea. How does concurrent updates work with the augumented trees? I have been thinking about the same for a while something like CouchDB but segment aggregations (monoid) augumented so we can do interval queries over time too. But the only thing bothering is augumented trees are notorious of contention on concurrent updates. Do you have any ideas on merging back if we have multiple versions of augumented trees.

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

#134

Post by yellowflash »

pacaro wrote: post #98
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-…

That's how mongodb geospatial indexes work IIRC

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

#135

Post by jordanmorgan10 »

So it’s not snazzy, but I also wrote Objective-C a long time without knowing about NSPointerArray.

Among other things, it can store nil values, which if you’ve written any Cocoa apps, is an all too common way to crash your software.

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

#137

Post by sicp-enjoyer »

jefftk wrote: post #109
NSMutableSet wrote: post #75

Earlier quoted context omitted.

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 shif…

C++ STL uses trees because the generic requirement for them to work is a Ironically, due to caches, sorting and then using algorithms that rely on order tend to be superior than most hashing implementations, even though they are theoretically worse due to log(n) factor. So in a way, C++ algorithms are actually more modern.

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

#138

Post by de6u99er »

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…

Ever heard of geospatial hierarchical Indices?

E.g. Uber's H3 index or Google's S2 index.

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

#139

Post by jfim »

jiggawatts wrote: post #131
itamarst wrote: post #80

Earlier quoted context omitted.

Does anyone actually use cache-oblivious data structure in practice? Not, like, "yes I know there's a cache I will write a datastructure for that", that's common, but specifically cache-oblivious data structures? People mention them a lot but I've never heard anyone say they actually used them.

To an extent, the B-Tree data structure (and its variants) are cache oblivious. They smoothly improve in performance with more and more cache memory, and can scale down to just megabytes of cache over terabytes of disk. The issue is that the last tree level tends to break this model because with some caching models it is "all or nothing" and is the biggest chunk of the data by far. There are workarounds which make it…

There are also Judy arrays: https://en.wikipedia.org/wiki/Judy_array

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

#140

Post by sicp-enjoyer »

sgtnoodle wrote: post #72
foolswisdom wrote: post #62

Earlier quoted context omitted.

Arrays aren't efficient when you want to add/remove to the head. Deque in python exists so there is a data structure with constant time pop/push to the head. And it is in fact implemented as a doubly linked list, with various optimizations: https://github.com/python/cpython/blob/v3.8.1/Modules/_colle... .

Neat, it's always best to look at the source. To be clear, a deque can be implemented on top of an array and still have constant time operations on the head.

If it's not constant time on both ends, it's not a deque. You can already insert items at any index in an array with linear cost.
Post reply on HN