Tree path majority data structures

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 τ ⋅ | P u v | times in the path P u v from u to v, where | P u v | denotes the number of nodes in P u v . 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 ⁡ lg w ⁡ σ ) query time, which is worst-case optimal for polylogarithmic-sized alphabets. We also describe two succinct-space solutions with query time O ( ( 1 / τ ) lg ⁎ ⁡ n lg ⁡ lg w ⁡ σ ) . One uses 2 n H + 4 n + o ( n ) ( H + 1 ) bits, where H ≤ lg ⁡ σ is the entropy of the label distribution; the other uses n H + O ( n ) + o ( n H ) bits. By using just o ( n lg ⁡ σ ) 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 τ ⋅ | P u v | times in P u v .