In this paper, we present a fast algorithm to answer range-sum queries in OLAP data cubes. Our algorithm supports constant-time queries while maintaining sub-linear time update and using minimum space. Furthermore, we study the trade-off between query time and update time. The complexity for query is O(2~(ld)) and for updates O((2~l ~(2~l)n~(2/1)d) on a data cube of n~d elements, where l is a trade-off parameter. Our algorithm improve over previous best known results.
展开▼
