News for hackers. Stuff that matters.
Re:Ask HN: What is your favorite data structure, what have y... by tptacek on Saturday October 03, 2015 @09:49AM (#10323870)
Aguri tries, which are bounded-sized radix trees with an LRU aggregation rule of joining sibling nodes.

The motivating use case is tracking metrics for IP addresses. You insert individual IP addresses into the tree, and when the tree fills, it starts rolling nodes for /32s into /31s, /30s, &c. Eventually, you get a picture of ranges of IP addresses in the data. That's neat, because, of course, IP packets themselves don't tell you anything about what subnets their IP addresses belong to.

The goofy thing I've done with them is apply them to memory addresses, so that I can collect individual pointers and bubble them up into allocation ranges, without instrumenting allocators.

Re:Ask HN: What is your favorite data structure, what have y... by semicolondev on Sunday October 04, 2015 @09:46PM (#10329583)
Sounds cool. Thanks for writing. I found some links to followup:

What is an Aguri tree? http://goo.gl/mBWdbJ (this question on SO mentions your comment from previous HN threads on data structures)

Aguri: Coolest Data Structure You've Never Heard Of https://news.ycombinator.com/item?id=101969

Aguri: An Aggregation-based Traffic Profiler http://goo.gl/zA4Vl8

//links shortened for length

Re:Ask HN: What is your favorite data structure, what have y... by seiji on Saturday October 03, 2015 @03:26PM (#10325049)
Does it collapse under IPv6?
Re:Ask HN: What is your favorite data structure, what have y... by tptacek on Sunday October 04, 2015 @08:50AM (#10327388)
Nope, should work fine. (The idea, I mean; I don't think there's an Aguri implementation that does v6 right now).