Faster Linear-Space Data Structures for Path Frequency Queries
This work improves query time bounds for fundamental frequency queries on trees, benefiting algorithms in data structures and computational geometry.
The authors present linear-space data structures for path mode, path least frequent element, and path α-minority queries on trees, achieving query times of O(√(n/w)) for the first two, improving over the previous O(log log n √(n/w)) bound, and O(α^{-1}) for α-minority, down from O(α^{-1} log log n).
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 \sqrt{nw})$ preprocessing time, that can answer path mode and path least frequent element queries in $O(\sqrt{n/w})$ time. This improves upon the best previously known bound of $O(\log\log n \sqrt{n/w})$ achieved by Durocher et al. 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. from $O(α^{-1}\log\log n)$ down to $O(α^{-1})$ by employing a simple randomized algorithm with a success probability $\geq 1/2$. We also present the first linear-space data structure supporting "Path Maximum $g$-value Color" queries in $O(\sqrt{n/w})$ time, requiring $O(n \sqrt{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\in Ω(\log n)$, where $w$ is the word size in bits.