Tree path majority data structures

Abstract

We present the first solution to finding tau-majorities on tree paths. Given a tree of nnodes, each with a label from [1..sigma], and a fixed threshold 0 < tau 1, such a query gives two nodes u nd v nd asks for all the labels that appear more than tau center dot vertical bar P-uv vertical bar times in the path P-uv from u to v, where vertical bar P-uv vertical bar 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 linearspace data structure with O((1/t) lg lg(w sigma)) query time, which is worst-case optimal for polylogarithmic-sized alphabets. We also describe two succinct-space solutions with query time O((1/tau) lg* n lglg(w sigma)). One uses 2nH+ 4n + o(n)(H+ 1) bits, where H <= lg sigma is the entropy of the label distribution; the other uses nH+ O(n) + O(nH) bits. By using just o(n lg sigma) extra bits, our succinct structures allow tau to be specified at query time. We obtain analogous results to find a tau-minority, that is, an element that appears between 1 and tau . vertical bar P-uv vertical bar times in P-uv.