 When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2018.68
URN: urn:nbn:de:0030-drops-100166
URL: http://drops.dagstuhl.de/opus/volltexte/2018/10016/
 Go to the corresponding LIPIcs Volume Portal

Tree Path Majority Data Structures

 pdf-format:

Abstract

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.

BibTeX - Entry

@InProceedings{gagie_et_al:LIPIcs:2018:10016,
author =	{Travis Gagie and Meng He and Gonzalo Navarro},
title =	{{Tree Path Majority Data Structures}},
booktitle =	{29th International Symposium on Algorithms and Computation  (ISAAC 2018)},
pages =	{68:1--68:12},
series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN =	{978-3-95977-094-1},
ISSN =	{1868-8969},
year =	{2018},
volume =	{123},
editor =	{Wen-Lian Hsu and Der-Tsai Lee and Chung-Shou Liao},
publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address =	{Dagstuhl, Germany},
URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/10016},
URN =		{urn:nbn:de:0030-drops-100166},
doi =		{10.4230/LIPIcs.ISAAC.2018.68},
annote =	{Keywords: Majorities on Trees, Succinct data structures}
}

 Keywords: Majorities on Trees, Succinct data structures Seminar: 29th International Symposium on Algorithms and Computation (ISAAC 2018) Issue Date: 2018 Date of publication: 27.11.2018

DROPS-Home | Imprint | Privacy 