Tree Path Majority Data Structures

2018/06/05 by Gagie, Travis, He, Meng, Navarro, Gonzalo
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1806.01804

Abstract

We present the first solution to τ-majorities on tree paths. Given a tree of n nodes, each with a label from [1..σ], and a fixed threshold 0 1, we can also build a structure that uses O(nlog^[κ] n) space, where log^[κ] n denotes the function that applies logarithm κ times to n, and answers queries in time O((1/τ)loglog_w σ). The construction time of both structures is O(nlog n). We also describe two succinct-space solutions with the same query time of the linear-space structure. One uses 2nH + 4n + o(n)(H+1) bits, where H ≤ \lgσ is the entropy of the label distribution, and can be built in O(nlog n) time. The other uses nH + O(n) + o(nH) bits and is built in O(nlog n) time w.h.p.

Related

• Properly learning decision trees in almost polynomial time
• Path Query Data Structures in Practice
• Representation of ordered trees with a given degree distribution
• Using statistical encoding to achieve tree succinctness never seen before
• Path and Ancestor Queries over Trees with Multidimensional Weight Vectors