Compressed Dynamic Range Majority and Minority Data Structures
Author
dc.contributor.author
Gagie, Travis
Author
dc.contributor.author
He, Meng
Author
dc.contributor.author
Navarro, Gonzalo
Admission date
dc.date.accessioned
2020-05-05T23:48:20Z
Available date
dc.date.available
2020-05-05T23:48:20Z
Publication date
dc.date.issued
2020
Cita de ítem
dc.identifier.citation
Algorithmica, 17 February 2020
es_ES
Identifier
dc.identifier.other
10.1007/s00453-020-00687-6
Identifier
dc.identifier.uri
https://repositorio.uchile.cl/handle/2250/174422
Abstract
dc.description.abstract
In the range alpha-majority query problem, we are given a sequence S[1 horizontal ellipsis n] and a fixed threshold alpha is an element of(0,1), and are asked to preprocess S such that, given a query range [i horizontal ellipsis j], we can efficiently report the symbols that occur more than alpha(j-i+1) times in S[i horizontal ellipsis j], which are called the range alpha-majorities. In this article we describe the first compressed dynamic data structure for range alpha-majority queries.
It represents S in compressed space-nHk+o(nlg sigma) bits for any k=o(lg sigma n), where sigma is the alphabet size and Hk <= H0 <= lg sigma is the kth order empirical entropy of S-and answers queries in amortized time. We then show how to modify our data structure to receive some beta >=alpha at query time and report the range beta-majorities in time, without increasing the asymptotic space or update-time bounds.
The best previous dynamic solution has the same query and update times as ours, but it occupies O(n) words and cannot take advantage of being given a larger threshold beta at query time. We also design the first dynamic data structure for range alpha-minority-i.e., find a non-alpha-majority that occurs in a range-and obtain space and time bounds similar to those for alpha-majorities. We extend the structure to find Theta(1/alpha)-minorities at the same space and time cost. By giving up updates, we obtain static data structures with query time O((1/alpha)lglgw sigma) for both problems, on a RAM with word size w=omega(lgn) bits, without increasing our space bound.
Static alternatives reach time O(1/alpha), but they compress S only to zeroth order entropy (H0) or they only handle small values of alpha, that is, lg(1/alpha)=o(lg sigma).
es_ES
Patrocinador
dc.description.sponsorship
Comision Nacional de Investigacion Cientifica y Tecnologica (CONICYT)
CONICYT FONDECYT
1-171058
Natural Sciences and Engineering Research Council of Canada
Comision Nacional de Investigacion Cientifica y Tecnologica (CONICYT)
FB0001
Millenium Institute for Foundational Research on Data, Chile