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. The mode of a multiset of labels, is a label that occurs at least as often as any other label. The input to the range mode problem is an array A of size n. A range query [i, j] must return the mode of the subarray A[i], A[i+1],...,A[j]. We prove that any data structure that uses S memory cells of w bits needs Ω(log n log(Sw n)) time to answer a range mode query. Secondly, we consider the related range k-frequency problem. The input to this problem is an array A of size n, and a query [i, j] must return whether there exists a label that occurs precisely k times in the subarray A[i], A[i+1],...,A[j]. We show that for any constant k > 1, this problem is equivalent to 2D orthogonal rectangle stabbing, and that for k = 1 this is no harder than four-sided 3D orthogonal range emptiness. Finally, we consider approximate range mode queries. A c-approximate range mode query must return a label that occurs at least 1 c times that of the mode. We describe a linear space data structure that supports 3-approximate range mode queries in constant time, and a data structure that uses O(n e) space and supports (1 + e)-approximation queries in O(log 1 e) time. Given a static array of @math totally ordered objects, the range minimum query problem is to build a data structure that allows us to answer efficiently subsequent on-line queries of the form “what is the position of a minimum element in the subarray ranging from @math to @math ?”. We focus on two settings, where (1) the input array is available at query time, and (2) the input array is available only at construction time. In setting (1), we show new data structures (a) of size @math bits and query time @math for any positive integer function @math for an arbitrary constant @math , or (b) with @math bits and @math query time, where @math denotes the empirical entropy of @math th order of the input array. In setting (2), we give a data structure of size @math bits and query time @math . All data structures can be constructed in linear time and almost in-place.