Faster Linear-Space Data Structures for Path Frequency Queries
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913048723193856 |
|---|---|
| author | Rata, Ovidiu |
| author_facet | Rata, Ovidiu |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_18667 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Faster Linear-Space Data Structures for Path Frequency Queries Rata, Ovidiu Data Structures and Algorithms E.1.7 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. |
| title | Faster Linear-Space Data Structures for Path Frequency Queries |
| topic | Data Structures and Algorithms E.1.7 |
| url | https://arxiv.org/abs/2604.18667 |