2004 | OriginalPaper | Chapter
Space-Efficient Range-Sum Queries in OLAP
Authors : Fredrik Bengtsson, Jingsen Chen
Published in: Data Warehousing and Knowledge Discovery
Publisher: Springer Berlin Heidelberg
Included in: Professional Book Archive
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
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ℓ d) and for updates $O((2^\ell \sqrt[2^\ell]{n})^d)$ on a data cube of nd elements, where ℓ is a trade-off parameter. Our algorithm improve over previous best known results.