前几天有朋友给我推荐github上的一个开源项目https://github.com/OhBonsai/RedisTree，可以直接用redis读写polytree的数据结构，还是挺有意思的。那么，什么是聚树？数据结构与树说到数据结构，我们脑海中可能会呈现出这样一棵树：也就是说，数据结构大致可以分为两类：线性数据结构和非线性数据结构。常见的线性数据结构有数组、链表、栈、队列；非线性数据结构主要是树和图。虽然不是bootstrapping，但我们实际上是用“树”来描述数据结构。树数据结构被定义为链接在一起以表示或模拟层次结构的对象或实体（称为节点）的集合。树数据结构是一种非线性数据结构，因为它不是按顺序存储的。它是一个层次结构，因为树中的元素排列在多个层次上。“树”中常用的术语大致有以下几种：根据树中子节点的数量和子节点本身的属性，形成各种树，树的应用场景非常广泛，比如计算机系统的文件系统，无论是简单的计算还是复杂的数学表达式，此时的树是一种特殊的树，称为表达式树，二叉树支持平均时间O(logN)的查找操作等等。polytree及其特性polytree一词是Rebane和Pearl在1987年创造的。Polytree是有向无环图的一种特殊情况，有向无环图是一种在任意两个顶点之间至多有一条无向路径的图。换句话说，有向无环图，其中从任何节点可达的子图形成一棵树。有向无环图请参考《有向无环图(DAG)的温故知新》。图是一个神奇的东西。图论是应用数学中应用极为广泛的范畴。在计算机科学中也是如此。它在日常生活中也非常广泛；图表；鄙视链也是一个图；网格实际上是一个图形，等等。不管是什么结构，只要结构中的对象之间存在二元联系，总能找到一个图来描述它，用一些有向边或无向边连接一些点，长短无所谓的边缘;if多元关系可以用超图表示。具体考虑一棵多叉树，线性预处理可以插入中间节点并折叠只有一个子节点的节点，从而产生一棵多叉树可用于回答对原始多叉树的查询，因此，在不失一般性的情况下，可以假设??刚好2度。对于每个节点，以任何拓扑顺序进行自下而上的线性时间预处理??我们将为节点构造一个索引结构，我们称之为“中缀树”，其中可能还包括指向其他??先前定义的此类结构的指针。Polytrees是在线性时间内构建的，对于任何节点，可以以恒定延迟枚举Polytree。中缀树中有三种节点：叶节点，标记有至少一个且至多四个元素的显式集合（它们是原始多元树的叶子）；小的内部节点，用显式元素标记并指向一个或两个节点的中缀树指针标记；大的内部节点，标有两个显式元素和指向一个或两个中缀树节点的指针。进一步要求中缀树中没有重复的元素，即对于每个节点??在中缀树中，P的每个叶子最多在标签中显示一次??。节点??在中缀树中，它是集合??(??)对P的叶子节点进行编码。中缀树的思想是通过保留一些显式元素，我们既可以在枚举时使用它们快速访问节点，也可以在合并时使用它们以便有足够的元素以适应标准中缀树新创建的节点。索引的数据结构将polytree的每个节点映射到一个可达的叶节点??(??)，而??(??(??))是??中的节点可达的叶节点集合。然后，可以获得Polytree的以下两个属性：这可以在线性时间内完成；枚举可以在不断的延迟中完成。多元树的应用多元树的典型应用之一是作为概率推理的图形模型。如果贝叶斯网络具有多元树结构，则可以有效地推理出使用置信度传播。事实上，polytree还有很多更具体的应用。例如，和弦音乐是一种共时的、离散的时间序列，通常表现为一维的事件序列，或二维的钢琴卷轴。缺点是音乐知识不够多，不能反映和弦音乐的内在结构。基于polytree的树结构包含三个层次：时间序列-笔记-笔记属性。然后使用编码器-解码器网络来学习和弦音乐的潜在表示。整体模型结构如下：钢琴表征学习任务的实验结果表明，polytree在重建精度和模型泛化方面均优于baseline。几乎同名的Prollytree，是IT界创造新名词的最爱，国内外几乎都是如此。为了创建一个类似git的去中心化数据库，Norms提出了ProllyTree。虽然读音差不多，但其实相差甚远。ProllyTree的全称是ProbabilisticMerkleB-Trees，融合了B-tree和merkletree。结构示例如下：因此，prollytree具有B-tree高效随机读写和有序扫描的特性，具有merkletree的可验证性和包含/排除的可证明性，具体属性见下表：Norms项目以prollytree为核心数据结构，是实现去中心化数据库的积极尝试。小结当我们觉得它没意思的时候，可能是因为我们对它缺乏了解；当我们觉得有趣的时候，也许我们才刚刚走在应用的路上。老码友对polytree的认知都是一样的，给定不同的约束，我们可以得到不同的树，然后应用到不同的业务场景中。参考分层Polytree网络的增量动态构建，https://arxiv.org/abs/1302.6833https://ldzhangyx.github.io/2019/10/30/polytree/https://www.microsoft.com/en-us/research/wp-content/uploads/2016/05/prml-slides-8.pdfhttps://cstheory.stackexchange.com/questions/37262/efficient-enumeration-of-the-reachable-leaves-of-节点-in-a-polytreehttps://github.com/attic-labs/noms
