Starting from the local structures to study hierarchical trees is a common research method. However, the cumbersome analysis and description make the naive method challenging to adapt to the increasingly complex hierarchical tree problems. To improve the efficiency of hierarchical tree research, we propose an embeddable matrix representation for hierarchical trees, called Generation Matrix. It can transform the abstract hierarchical tree into a concrete matrix representation and then take the hierarchical tree as a whole to study, which dramatically reduces the complexity of research. Mathematical analysis shows that Generation Matrix can simulate various recursive algorithms without accessing local structures and provides a variety of interpretable matrix operations to support the research of hierarchical trees. Applying Generation Matrix to differential privacy hierarchical tree release, we propose a Generation Matrix-based optimally consistent release algorithm (GMC). It provides an exceptionally concise process description so that we can describe its core steps as a simple matrix expression rather than multiple complicated recursive processes like existing algorithms. Our experiments show that GMC takes only a few seconds to complete a release for large-scale datasets with more than 10 million nodes. The calculation efficiency is increased by up to 100 times compared with the state-of-the-art schemes.
翻译:从当地结构开始研究等级树是一种常见的研究方法。然而,繁琐的分析和描述使得适应日益复杂的等级树问题这一天真的方法难以适应日益复杂的等级树问题。为了提高等级树研究的效率,我们提议对等级树进行嵌入式矩阵说明,称为“世代矩阵”。它可以将抽象的等级树变成一个具体的矩阵说明,然后将等级树作为一个整体来研究,这大大降低了研究的复杂性。数学分析表明,一代矩阵可以模拟各种递归算法,而不必接触当地结构,并提供各种可解释的矩阵操作以支持等级树的研究。为了将代母矩阵用于区分隐私等级树的释放,我们提议以代父矩阵为基础的最佳一致释放算法(GMC)。它提供了非常简洁的过程描述,以便我们可以将其核心步骤描述为简单的矩阵表示,而不是像现有算法那样的多重复杂的循环过程。我们的实验表明,GMC只需几秒钟就能完成1000万节点以上的大规模数据集的释放。计算效率比州计划提高了100倍。