Faster Linear-Space Data Structures for Path Frequency Queries

We present linear-space data structures for several frequency queries on trees, namely: path mode, path least frequent element, and path α-minority queries. We present the first linear-space data structures, requiring O(n √{nw}) preprocessing time, that can answer path mode and path least frequent element queries in O(√{n/w}) time. This improves upon the best previously known bound of O(log log n √{n/w}) achieved by Durocher et al. [Durocher et al., 2016] in 2016. For the path α-minority problem, where α is specified at query time, we reduce the query time of the linear-space data structure of Durocher et al. [Durocher et al., 2016] from O(α⁻¹log log n) down to O(α⁻¹) by employing a simple randomized algorithm with a success probability ≥ 1/2. We also present the first linear-space data structure supporting "Path Maximum g-value Color" queries in O(√{n/w}) time, requiring O(n √{nw}) preprocessing time. This general framework encapsulates both path mode and path least frequent element queries. For our data structures, we consider the word-RAM model with w ∈ Ω(log n), where w is the word size in bits.