Generation matrix: an embeddable matrix representation for hierarchical trees

DOI10.1016/J.TCS.2023.114180MaRDI QIDQ6057832zbMATH OpenOpenAlexFDO

Authors Jianping Cai, Ximeng Liu, Jiayin Li, S. Y. Zhang

Publication date 26 October 2023

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2201.11297

zbMATH Keywords

consistencydifferential privacygeneration matrixhierarchical treematrix representation

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: 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.

Recommendations

• scientific article; zbMATH DE number 7732142
• Tree embeddings
• Tree self-embeddings
• Generating random spanning trees via fast matrix multiplication
• Construction and complexity of hierarchical matrices
• scientific article; zbMATH DE number 5942279
• A fast algorithm for constructing trees from distance matrices
• On generating \(k\)-ary trees in computer representation

Cites work

• An interior point-proximal method of multipliers for convex quadratic programming
• scientific article; zbMATH DE number 6016068 (Why is no real title available?)
• Linear algebra and learning from data
• Matrix differential calculus with applications in statistics and econometrics
• Rounding error analysis of mixed precision block Householder QR algorithms
• Succinct representation of dynamic trees
• The ancestral matrix of a rooted tree
• Trees with extremal spectral radius of weighted adjacency matrices among trees weighted by degree-based indices
• Triangular matrix representations
• Ultra-succinct representation of ordered trees with applications

This page was built for publication: Generation matrix: an embeddable matrix representation for hierarchical trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6057832)