View publication
| Title | Tree Path Majority Data Structures |
| Authors | Travis Gagie, Meng He, Gonzalo Navarro, Carlos Ochoa |
| Publication date | 2020 |
| Abstract |
We present the first solution to finding 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 log_w s) query time, which is worst-case optimal for polylogarithmic-sized alphabets. We also describe two succinct-space solutions with query time O((1/t) log* n log log_w s). One uses 2nH + 4n + o(n)(H+1) bits, where H ≤ lg s is the entropy of the label distribution; the other uses nH + O(n) + o(nH) bits. By using just o(n log s) extra bits, our succinct structures allow t to be specified at query time. We obtain analogous results to find a t-minority, that is, an element that appears between 1 and t |P_uv| times in P_uv. |
| Downloaded | 7 times |
| Pages | 107-119 |
| Volume | 833 |
| Journal name | Theoretical Computer Science |
| Publisher | Elsevier Science (Amsterdam, The Netherlands) |
|
|
| Reference URL |
|