Compressed Dynamic Range Majority Data Structures

Abstract

In the range α-majority query problem, we preprocess a given sequence S[1.n] for a fixed threshold α ϵ (0, 1], such that given a query range [i.j], the symbols that occur more than α (j-i+1) times in S[i.j] can be reported efficiently. We design the first compressed solution to this problem in dynamic settings. Our data structure represents S using nHk o(nlg σ) bits for any k = o(log σ n), where σ is the alphabet size and Hk is the k-Th order empirical entropy of S. It answers range α-majority queries in O(lgn/αlg lgn) time, and supports insertions and deletions in O(lgn/α) amortized time. The best previous solution [1] has the same query and update times, but uses O(n) words.