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.