Tree Path Majority Data Structures
Travis Gagie, Meng He, and Gonzalo Navarro
We present the first solution to t-majorities on tree paths. Given a
tree of n nodes, each with a label from [1..s], and a fixed threshold
0 <t<1, such a query gives two nodes u and v and asks for all the
labels that appear more than t * |P_uv| times in the path
P_uv from u to v, where |P_uv| denotes the number of nodes in
P_uv.
Note that the answer to any query is of size up to
1/t.
On a w-bit RAM,
we obtain a linear-space data structure
with O((1/t) log* n log log_w s) query time.
For any k > 1, we can also build a structure that uses
O(n log[r] n) space, where log[r] n denotes the function
that applies logarithm r times to n,
and answers queries in time O((1/t) log log_w s).
The construction time of both structures is O(n log 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 s is the entropy of the label distribution,
and can be built in O(n log n) time. The other uses nH + O(n) +
o(nH) bits
and is built in O(n log n) randomized time.