Abstract
We consider the dynamic range minimum problem on the ultra-wide word RAM model of computation. This model extends the classic w-bit word RAM model with special ultrawords of length w2 bits that support standard arithmetic and boolean operation and scattered memory access operations that can access w (non-contiguous) locations in memory. The ultra-wide word RAM model captures (and idealizes) modern vector processor architectures.
Our main result is a linear space data structure that supports range minimum queries and updates in O(log log log n) time. This exponentially improves the time of existing techniques. Our result is based on a simple reduction to prefix minimum computations on sequences O(log n) words combined with a new parallel, recursive implementation of these.
Our main result is a linear space data structure that supports range minimum queries and updates in O(log log log n) time. This exponentially improves the time of existing techniques. Our result is based on a simple reduction to prefix minimum computations on sequences O(log n) words combined with a new parallel, recursive implementation of these.
| Original language | English |
|---|---|
| Title of host publication | Proceedings of the 50th International Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2025 |
| Publisher | Springer |
| Publication date | 2025 |
| Pages | 122-135 |
| ISBN (Print) | 978-3-031-82669-6 |
| ISBN (Electronic) | 978-3-031-82670-2 |
| DOIs | |
| Publication status | Published - 2025 |
| Event | 50th International Conference on Current Trends in Theory and Practice of Computer Science - Bratislava, Slovakia Duration: 20 Jan 2025 → 23 Jan 2025 |
Conference
| Conference | 50th International Conference on Current Trends in Theory and Practice of Computer Science |
|---|---|
| Country/Territory | Slovakia |
| City | Bratislava |
| Period | 20/01/2025 → 23/01/2025 |
Keywords
- Ultra-wide word RAM model
- Range minimum queries
- Prefix minimum