EXACT AND APPROXIMATE RANGE MODE QUERY DATA STRUCTURES IN PRACTICE

Abstract

We conduct an experimental study on the range mode problem. In the exact version of the problem, we preprocess an array A, such that given a query range [a, b], the most frequent element in A[a, b] can be found efficiently. For this problem, our most important finding is that the strategy of using succinct data structures to encode more precomputed information not only helped Chan et al. (Linear-space data structures for range mode query in arrays, Theory of Computing Systems, 2013) improve previous results in theory but also helps us achieve the best time/space tradeoff in practice; we even go a step further to replace more components in the solution of Chan et al. with succinct data structures. In the approximate version of this problem, a (1 + ϵ)-approximate range mode query looks for an element whose occurrences in A[a, b] is at least Fa,b/(1 + ϵ), where Fa,b is the frequency of the mode in A[a, b]. We implement all previous solutions to this problem and find that, even when ϵ = 1/2, the average approximation ratio of these solutions is close to 1 in practice while providing a much faster query time than the best exact solution. Among these solutions, El-Zein et al. (On Approximate Range Mode and Range Selection, 30th International Symposium on Algorithms and Computation, 2019) provides us with one solution that takes only 35.6% ∼ 93.8% space cost of the input array of 32-bit integers (in most cases, the space cost is closer to the lower end). Its non-succinct version also stands out with query support at least several times faster than other O(n/ε)-word structures while using only slightly more space in practice.