pipette
ENEnglish

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

Filippo di Gravina

Preprint con versión publicada

En palabras de los autores

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.

Resultado principalEl resumen no menciona limitaciones.

Apareció: martes, 20 de octubre. arXiv. Preprint con versión publicada.

DOI: 10.5281/zenodo.23300993

Versión publicada: 10.5281/zenodo.23300993

Comentario de los autores: 18 pages, 0 figures