A mode of a multiset @math is an element @math of maximum multiplicity; that is, @math occurs at least as frequently as any other element in @math . Given a list @math of @math items, we consider the problem of constructing a data structure that efficiently answers range mode queries on @math . Each query consists of an input pair of indices @math for which a mode of @math must be returned. We present an @math -space static data structure that supports range mode queries in @math time in the worst case, for any fixed @math . When @math , this corresponds to the first linear-space data structure to guarantee @math query time. We then describe three additional linear-space data structures that provide @math , @math , and @math query time, respectively, where @math denotes the number of distinct elements in @math and @math denotes the frequency of the mode of @math . Finally, we examine generalizing our data structures to higher dimensions.
@cite_33 consider approximate range mode queries, in which the objective is to return an element whose frequency is at least @math . They give a data structure that requires @math space and answers approximate range mode queries in @math time for any fixed @math , as well as data structures that provide constant-time queries for @math , using space @math , @math , and @math , respectively. @cite_37 give a linear-space data structure that supports approximate range mode queries in constant time for @math , and an @math -space data structure that supports approximate range mode queries in @math time for any fixed @math .
@cite_37 @cite_33
1550061821 2111741778
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 @math space, our data structure can find in @math 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 @math 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 @math and at most @math is returned for 0<<1. We consider range queries that search for low-frequency elements (least frequent elements and @math ?-minorities) in arrays. An @math ?-minority of a query range has multiplicity no greater than an @math ? fraction of the elements in the range. Our data structure for the least frequent element range query problem requires @math O(n) space, @math O(n3 2) preprocessing time, and @math O(n) query time. A reduction from boolean matrix multiplication to this problem shows the hardness of simultaneous improvements in both preprocessing time and query time. Our data structure for the @math ?-minority range query problem requires @math O(n) space, supports queries in @math O(1 ?) time, and allows @math ? to be specified at query time.