Efficient Range-Sum Queries along Dimensional Hierarchies in Data Cubes

Author

Lauer, Tobias ; Mai, Dominic ; Hagedorn, Philippe

Author_Institution

Jedox AG, Freiburg

fYear

2009

fDate

1-6 March 2009

Firstpage

7

Lastpage

12

Abstract

Fast response to userspsila query and update requests continues to be one of the key requirements for OLAP systems. We outline the generalization of a space-efficient data structure, which makes it particularly suited for cubes with hierarchically structured dimensions. For a large class of range-sum queries - roll-up and drill-down along dimension hierarchies - the structure requires only a constant number of cell accesses per query on average, while offering an expected poly-logarithmic update performance.

Keywords

data mining; data structures; query processing; OLAP system; data cube; dimensional hierarchy; poly-logarithmic update performance; range-sum query; space-efficient data structure; update request; Aggregates; Algorithm design and analysis; Data analysis; Data structures; Databases; Delay; Iterative algorithms; Marketing and sales; Runtime; Time measurement; OLAP; average-case analysis; data cube; pre-aggregation; range-sum query; updates;

fLanguage

English

Publisher

ieee

Conference_Titel

Advances in Databases, Knowledge, and Data Applications, 2009. DBKDA '09. First International Conference on

Conference_Location

Gosier

Print_ISBN

978-1-4244-3467-1

Electronic_ISBN

978-0-7695-3550-0

Type

conf

DOI

10.1109/DBKDA.2009.18

Filename

5071805