Approximate range mode and range median queries
We consider data structures and algorithms for preprocessing a labelled list of length n so that, for any given indices i and j we can answer queries of the form: What is the mode or median label in the sequence of labels between indices i and j. Our results are on approximate versions of this problem. Using O(n/1-α) space, our data structure can find in O (log log 1/α n) time an element whose number of occurrences is at least α times that of the mode, for some user-specified parameter 0 < α < 1. Data structures are proposed to achieve constant query time for α = 1/2, 1/3 and 1/4, using storage space of O(n log n), O(n log log n) and O(n), respectively. Finally, if the elements are comparable, we construct an O(n/1-α) space data structure that answers approximate range median queries. Specifically, given indices i and j, in O(1) time, an element whose rank is at least α × [|j - i+ 1|/2] and at most (2 - α) × [|j - i + 1|/2] is returned for 0 < α < 1.
|22nd Annual Symposium on Theoretical Aspects of Computer Science, STACS 2005|
|Organisation||School of Computer Science|
Bose, P, Kranakis, E, Morin, P, & Tang, Y. (Yihui). (2005). Approximate range mode and range median queries. Presented at the 22nd Annual Symposium on Theoretical Aspects of Computer Science, STACS 2005.