Tree Path Majority Data Structures

Abstract

We present the first solution to $\tau$-majorities on tree paths. Given a tree of $n$ nodes, each with a label from $[\mathrm{1..}\sigma ]$, and a fixed threshold $0<\tau <1$, such a query gives two nodes $u$ and $v$ and asks for all the labels that appear more than $\tau \cdot |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/\tau$. On a $w$-bit RAM, we obtain a linear-space data structure with $O((1/\tau ){\log }^{\ast }n\log {\log }_w\sigma )$ query time. For any $\kappa >1$, we can also build a structure that uses $O(n{\log }^{[\kappa ]}n)$ space, where ${\log }^{[\kappa ]}n$ denotes the function that applies logarithm $\kappa$ times to $n$, and answers queries in time $O((1/\tau )\log {\log }_w\sigma )$. 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\le \lg \sigma$ 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)$ time w.h.p.