Optimal Range Max Datacube for Fixed Dimensions Chung Keung Poon   View Paper (PDF)   Return to Research Papers Abstract We present a new data structure to support orthogonal range max queries on a datacube. For a d-dimensional datacube with size n in each dimension where $d \leq c_3 \log\log n / \log(\log^* n)$, our structure requires $O(c_1^d)$ query time and $O((c_2 n)^d)$ storage where c1, c2 and c3 are constants independent of d and n; and $\log^* n$ is the minimum number of repeated logarithms it takes to reduce the value $n$ to at most 2. Hence our data structure is asymptotically optimal when d is fixed, i.e., a constant independent of n. ©2004 Association for Computing Machinery