2026-07-23T03:28:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10016 2024-03-06T10:45:21Z ddc:004 open_access

Tree Path Majority Data Structures Gagie, Travis He, Meng Navarro, Gonzalo Majorities on Trees Succinct data structures We present the first solution to tau-majorities on tree paths. Given a tree of n nodes, each with a label from [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 * |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)lg^* n lg lg_w sigma) query time. For any kappa > 1, we can also build a structure that uses O(n lg^{[kappa]} n) space, where lg^{[kappa]} n denotes the function that applies logarithm kappa times to n, and answers queries in time O((1/tau)lg lg_w sigma). The construction time of both structures is O(n lg 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 <=lg sigma is the entropy of the label distribution, and can be built in O(n lg n) time. The other uses nH + O(n) + o(nH) bits and is built in O(n lg n) time w.h.p. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Travis Gagie and Meng He and Gonzalo Navarro 2018 Is Part Of LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2018.68 urn:nbn:de:0030-drops-100166 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.68 eng https://creativecommons.org/licenses/by/3.0/legalcode