2004 | OriginalPaper | Buchkapitel
Space-Efficient Range-Sum Queries in OLAP
verfasst von : Fredrik Bengtsson, Jingsen Chen
Erschienen in: Data Warehousing and Knowledge Discovery
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. 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.