Compressed Dynamic Range Majority and Minority Data Structures

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).