Fast algorithm finds mode frequencies for many range queries
Batch range mode in O(n+Q)^1.395
Data Structures and Algorithms
Summary
Finding the most frequent item (mode) in different parts of a long list can take a lot of time, especially if you have many questions about different parts. The authors present a new method that solves many such questions much faster than previous approaches. They use advanced math techniques and clever ways to organize data to do this efficiently and exactly. Their method works for any number of queries and array sizes, always giving the correct results quickly.
What this means in practice
- •For database engineers: Speed up processing of batch queries asking for mode frequencies over data intervals using a new exact algorithm with better worst-case guarantees.
- •For data analytics teams: Improve performance of analytics tasks that require calculating modes over many data segments precisely and efficiently without approximations.
Authors
Filippo di Gravina
Abstract
We give a deterministic worst-case algorithm for exact Batched Range Mode on an arbitrary array of length n and a batch of Q intervals. The algorithm returns the mode frequency and the smallest mode identifier for each query in time (n+Q)^(tau+o(1)), where tau = 5 - sqrt(13) = 1.394448724536... . The algorithm combines virtual occurrence windows and block-boundary snapping with a query-restricted min-plus product whose first operand is column-monotone and whose second operand is row-monotone. A deterministic modular verifier uses geometric and query potentials to bound the same active regions; false modular matches are corrected by offline orthogonal range updates. The final analysis uses the sharper rectangular exponent curve of Uznanski (2026), together with exact rational parameter balancing and a transfer to prime fields. The analysis covers every frequency scale and arbitrary batch sizes. Exact frequencies and the smallest mode identifiers are recovered without increasing the exponent.