20050912
Approximate range mode and range median queries
Publication
Publication
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 userspecified 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.
Additional Metadata  

Conference  22nd Annual Symposium on Theoretical Aspects of Computer Science, STACS 2005 
Citation 
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.
