pipette
ESEspañol

Batch range mode in O(n+Q)^1.395

Filippo di Gravina

Preprint with a published version

In the authors' words

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.

Main resultThe abstract does not state a limitation.

Appeared: Tuesday, October 20. arXiv. Preprint with a published version.

DOI: 10.5281/zenodo.23300993

Published version: 10.5281/zenodo.23300993

Authors' comment: 18 pages, 0 figures