Abstract

We present the first solution to finding τ-majorities on tree paths. Given a tree of n nodes, each with a label from [1.σ], and a fixed threshold 0<τ<1, such a query gives two nodes u and v and asks for all the labels that appear more than τ⋅|Puv| times in the path Puv from u to v, where |Puv| denotes the number of nodes in Puv. Note that the answer to any query is of size up to 1/τ. On a w-bit RAM, we obtain a linear-space data structure with O((1/τ)lg⁡lgw⁡σ) query time, which is worst-case optimal for polylogarithmic-sized alphabets. We also describe two succinct-space solutions with query time O((1/τ)lg⁎⁡nlg⁡lgw⁡σ). One uses 2nH+4n+o(n)(H+1) bits, where H≤lg⁡σ is the entropy of the label distribution; the other uses nH+O(n)+o(nH) bits. By using just o(nlg⁡σ) extra bits, our succinct structures allow τ to be specified at query time. We obtain analogous results to find a τ-minority, that is, an element that appears between 1 and τ⋅|Puv| times in Puv.