了解融合树？ [英] Understanding Fusion Trees?

问题描述

我偶然发现了维基百科页面：

融合树

$ b $我阅读了底部链接的课堂笔记pdf，但是它对数据结构本身有一些波动，并且详细介绍了 sketch（x）函数。我认为我的一些困惑是文章试图非常笼统，我想要一个具体的例子可视化。

这个数据结构是否适合存储数据基于任意的32位或64位整数键？它与B树有什么不同？有一个部分说它基本上是一个分支因子 B =（lg n）^（1/5）的B树。对于一个拥有32位密钥的完全填充的树，B将为2.这只是一个二叉树吗？这个数据结构旨在使用更长的位串作为键？

我的谷歌没有提出任何非常有用的东西，但我欢迎任何良好的链接话题。这实际上只是一个过去的好奇心，所以我不愿意在 portal.acm.org 支付PDF。

解决方案

我已经阅读（只是一个快速通过）的创意论文，似乎很有趣。您也可以在第一页回答大部分的问题。

您可以从 here

HTH！

I stumbled across the Wikipedia page for them:

Fusion tree

And I read the class notes pdfs linked at the bottom, but it gets hand-wavy about the data structure itself and goes into a lot of detail about the sketch(x) function. I think part of my confusion is that the papers are trying to be very general, and I would like a specific example to visualize.

Is this data structure appropriate for storing data based on arbitrary 32 or 64 bit integer keys? How does it differ from a B-tree? There is one section that says it's basically a B-tree with a branching factor B = (lg n)^(1/5). For a fully populated tree with 32 bit keys, B would be 2. Does this just become a binary tree? Is this data structure intended to use much longer bit-strings as keys?

My Googling didn't turn up anything terribly useful, but I would welcome any good links on the topic. This is really just a passing curiosity, so I haven't been willing to pay for the PDFs at portal.acm.org yet.

解决方案

I've read (just a quick pass) the seminal paper and seems interesting. It also answers most of your questions in the first page.

You may download the paper from here

HTH!

这篇关于了解融合树？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！