Enumerating Range Modes
This work addresses a computational geometry/data structures problem for researchers and practitioners needing efficient query processing on sequences, but it appears incremental as it builds on known problems with no mention of broad impact.
The paper tackles the range mode problem, which involves finding items with maximum frequency within a query range in a sequence, and its generalization to range mode enumeration, achieving algorithms with query time complexities linear to the output size plus small terms.
We consider the range mode problem where given a sequence and a query range in it, we want to find items with maximum frequency in the range. We give time- and space- efficient algorithms for this problem. Our algorithms are efficient for small maximum frequency cases. We also consider a natural generalization of the problem: the range mode enumeration problem, for which there has been no known efficient algorithms. Our algorithms have query time complexities which is linear to the output size plus small terms.