×

Generation matrix: an embeddable matrix representation for hierarchical trees. (English) Zbl 07755510

Summary: 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, dramatically reducing the research complexity. 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.

MSC:

68Qxx Theory of computing

Software:

TensorFlow; HopsFS; Caffe

References:

[1] Niazi, S.; Ismail, M.; Grohsschmiedt, S.; Ronstrm, M.; Haridi, S.; Dowling, J., Hopsfs: Scaling Hierarchical File System Metadata Using Newsql Databases (2016)
[2] Abowd, J., The U.S. Census Bureau Adopts Differential Privacy, 2867 (2018)
[3] Lima, T.; de Aguiar, M., Laplacian Matrices for Extremely Balanced and Unbalanced Phylogenetic Trees (2020)
[4] Garfinkel, S.; Abowd, J.; Powazek, S., Issues encountered deploying differential privacy (2018)
[5] Li, X.; Wang, Z., Trees with extremal spectral radius of weighted adjacency matrices among trees weighted by degree-based indices. Linear Algebra Appl. (2021) · Zbl 1462.05232
[6] Ganesh, S.; Mohanty, S., Trees with Matrix Weights: Laplacian Matrix and Characteristic-Like Vertices (2020)
[7] Bapat, R.; Sivasubramanian, S., Squared distance matrix of a tree: inverse and inertia. Linear Algebra Appl. (2015)
[8] Andriantiana, E.; Dadedzi, K.; Wagner, S., The ancestral matrix of a rooted tree. Linear Algebra Appl., 35-65 (2019) · Zbl 1483.05091
[9] Fulton, W.; Harris, J., Graduate texts in mathematics
[10] Zhou, J.; Cui, G.; Hu, S.; Zhang, Z.; Yang, C.; Liu, Z.; Wang, L.; Li, C.; Sun, M., Graph neural networks: a review of methods and applications. AI Open, 57-81 (2020)
[11] Chen, X. A., Understanding Spectral Graph Neural Network (2020)
[12] Deveci, M.; Trott, C.; Rajamanickam, S., Multi-threaded sparse matrix-matrix multiplication for many-core and gpu architectures. Parallel Comput. (2018)
[13] Hay, M.; Rastogi, V.; Miklau, G.; Suciu, D., Boosting the accuracy of differentially-private histograms through consistency. Proc. VLDB Endow. (2009)
[14] Wang, N.; Xiao, X.; Yang, Y.; Hoang, T.; Shin, H.; Shin, J.; Yu, G., Privtrie: Effective Frequent Term Discovery Under Local Differential Privacy, 821-832 (2018)
[15] Jansson, J.; Sadakane, K.; Sung, W.-K., Ultra-succinct representation of ordered trees with applications. J. Comput. Syst. Sci., 619-631 (2012) · Zbl 1242.68083
[16] Tsur, D., Succinct representation of labeled trees. Theor. Comput. Sci. (2013)
[17] Farzan, A.; Munro, J., Succinct representation of dynamic trees. Theor. Comput. Sci., 2668-2678 (2011) · Zbl 1220.68072
[18] Dwork, C.; McSherry, F.; Nissim, K.; Smith, A., Calibrating noise to sensitivity in private data analysis. J. Priv. Confid., 17-51 (2017)
[19] Qardaji, W.; Yang, W.; Li, N., Understanding hierarchical methods for differentially private histograms. Proc. VLDB Endow., 1954-1965 (2013)
[20] Cormode, G.; Procopiuc, M.; Shen, E.; Srivastava, D.; Yu, T., Differentially private spatial decompositions
[21] Yuan, S.; Pi, D.; Zhao, X.; Xu, M., Differential privacy trajectory data protection scheme based on r-tree. Expert Syst. Appl. (2021)
[22] Lee, J.; Wang, Y.; Kifer, D., Maximum Likelihood Postprocessing for Differential Privacy Under Consistency Constraints, 635-644 (2015)
[23] Strang, G., Linear Algebra and Learning from Data (2019), Wellesley-Cambridge Press: Wellesley-Cambridge Press Cambridge · Zbl 1422.15001
[24] Birkenmeier, G.; Heatherly, H.; Kim, J.; Park, J., Triangular matrix representations. J. Algebra, 558-595 (2000) · Zbl 0964.16031
[25] Minah, L.; Fox, A.; Sanders, G., Rounding error analysis of mixed precision block Householder QR algorithms. SIAM J. Sci. Comput., A1723-A1753 (2021) · Zbl 1512.65066
[26] Desai, P.; Aslan, S.; Saniie, J., FPGA Implementation of Gram-Schmidt QR Decomposition Using High Level Synthesis, 482-487 (2017)
[27] Fam, W.; Alimohammad, A., Givens rotation-based QR decomposition for mimo systems. IET Commun. (2017)
[28] Stanley, R., Enumerative Combinatorics, vol. 1 (2012) · Zbl 1247.05003
[29] Pougkakiotis, S.; Gondzio, J., An interior point-proximal method of multipliers for convex quadratic programming. Comput. Optim. Appl. (2021) · Zbl 1469.90158
[30] M. C.M. incorporates LAPACK, Increasing the Speed and Capabilities of Matrix Computation (2000), [Online]
[31] Abadi, M.; Agarwal, A.; Barham, P.; Brevdo, E.; Chen, Z.; Citro, C.; Corrado, G.; Davis, A.; Dean, J.; Devin, M.; Ghemawat, S.; Goodfellow, I.; Harp, A.; Irving, G.; Isard, M.; Jia, Y.; Kaiser, L.; Kudlur, M.; Levenberg, J.; Zheng, X., Tensorflow: Large-Scale Machine Learning on Heterogeneous Distributed Systems (2015)
[32] Jia, Y.; Shelhamer, E.; Donahue, J.; Karayev, S.; Long, J.; Girshick, R.; Guadarrama, S.; Darrell, T., Caffe: convolutional architecture for fast feature embedding
[33] Magnus, J., Matrix differential calculus with applications in statistics and econometrics (2019) · Zbl 1411.15003
[34] Bureau, U. C., 2010 census summary file 1 (2012)
[35] New York city taxi data
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.