Faster Linear-Space Data Structures for Path Frequency Queries

arXiv:2604.18667v1 Announce Type: new
Abstract: We present linear-space data structures for several frequency queries on trees, namely: path mode, path least frequent element, and path $alpha$-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(loglog n sqrt{n/w})$ achieved by Durocher et al. in 2016.
For the path $alpha$-minority problem, where $alpha$ is specified at query time, we reduce the query time of the linear-space data structure of Durocher et al. from $O(alpha^{-1}loglog n)$ down to $O(alpha^{-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 $win Omega(log n)$, where $w$ is the word size in bits.