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. BIBTEX  Lecture Notes in Computer Science  Publisher: Springer-Verlag Heidelberg  ISSN: 0302-9743  Subject:  Computer Science  Volume 2572 / 2003  Title:  : Database Theory - ICDT 2003: 9th International Conference Siena, Italy, January 8-10, 2003. Proceedings  Editors:  D. Calvanese, M. Lenzerini, R. Motwani (Eds.) :  Chapter: pp. 158 - 172 }, ©2005 Association for Computing Machinery