text: 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_28: Given a list of n items and a function defined over sub-lists, we study the space required for computing the function for arbitrary sub-lists in constant time. For the function mode we improve the previously known space bound O(n^2 logn) to O(n^2loglogn log^2n) words. For median the space bound is improved to O(n^2loglog^2n log^2n) words from O(n^2@?log^(^k^)n logn), where k is an arbitrary constant and log^(^k^) is the iterated logarithm.
  @cite_37: 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.
  @cite_10: We consider algorithms for preprocessing labelled lists and trees so that, for any two nodes u and v we can answer queries of the form: What is the mode or median label in the sequence of labels on the path from u to v.
  @cite_8: We investigate the following problem: Given a list of n items and a function defined over lists of these items, generate a bounded amount of auxiliary information such that range queries asking for the value of the function on sub-lists can be answered within a certain time bound. For the function "mode" we improve the previously known time bound O(nƐ log n) to O(nƐ) with space O(n2-2Ɛ), where 0 ≤ Ɛ < 1 2. We improve the space bound O(n2 log log n log n) for an O(1) time bounded solution to O(n2 log n). For the function "median" the space bound O(n2 log log n log n) is improved to O(n2 log(k) n log n) for an O(1) time solution, where k is an arbitrary constant and log(k) is the iterated logarithm.
summary: Range Mode Query Naturally, a mode of the query interval @math can be computed directly without preprocessing using any of the methods described in . @cite_10 describe data structures that provide constant-time queries using @math space and @math -time queries using @math space, for any fixed @math . Petersen and Grabowski @cite_28 improve the first bound to constant time and @math space and Petersen @cite_8 improves the second bound to @math -time queries using @math space, for any fixed @math . When @math , the data structure of @cite_10 requires only linear space and provides @math query time. Although its space requirement is almost linear in @math as @math approaches @math , the data structure of Petersen @cite_8 requires @math space. Furthermore, the construction becomes impractical as @math approaches @math (the number of levels in a hierarchical set of tables and hash functions approaches @math as @math ) and no obvious modification reduces its space requirement to @math . @cite_37 prove a lower bound of @math query time for any data structure that uses @math memory cells of @math bits.