Tree path majority data structures
Artículo
Open/ Download
Access note
Acceso Abierto
Publication date
2020
Author
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.
Patrocinador
Comisión Nacional de Investigación Científica y Tecnológica (CONICYT)
CONICYT FONDECYT
1171058
1170048
Natural Sciences and Engineering Research Council of Canada
basal funds, CONICYT, Chile
FB0001
Millennium Institute for Foundational Research on Data (IMFD), Chile
Indexation
Artículo de publicación ISI Artículo de publicación SCOPUS
Quote Item
Theoretical Computer Science Vol. 833, 12 (2020), 107-119
Collections
The following license files are associated with this item: