Book chapter
An Efficient Algorithm for Computing Range-Groupby Queries
Database Systems for Advanced Applications, pp 483-497
2006
Abstract
Aggregation queries for arbitrary regions in an n-dimensional space are powerful tools for data analysis in OLAP. A GROUP BY query in OLAP is very important since it allows us to summarize various trends along with any combination of dimensions. In this paper, we extend the previous aggregation queries by including the GROUP BY clause for arbitrary regions. We call the extension range-groupby queries and present an efficient algorithm for processing them. A typical method of achieving fast response time for aggregation queries is using the prefix-sum array, which stores precomputed partial aggregation values. A naive method for range-groupby queries maintains a prefix-sum array for each combination of the grouping dimensions in an n-dimensional cube, which incurs enormous storage overhead. Our algorithm maintains only one prefix-sum array and still effectively processes range-groupby queries for all possible combinations of multiple grouping dimensions. Compared with the naive method, our algorithm reduces the space overhead by \documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$O(\frac{1}{2^n})$\end{document}, while accessing almost the identical number of cells.
Metrics
8 Record Views
1 citations in Scopus
Details
- Title
- An Efficient Algorithm for Computing Range-Groupby Queries
- Creators
- Young-Koo Lee - Korea Advanced Institute of Science and TechnologyWoong-Kee Loh - Korea Advanced Institute of Science and TechnologyYang-Sae Moon - Kangwon National UniversityKyu-Young Whang - Korea Advanced Institute of Science and TechnologyIl-Yeol Song - Drexel University
- Publication Details
- Database Systems for Advanced Applications, pp 483-497
- Series
- Lecture Notes in Computer Science
- Publisher
- Springer Berlin Heidelberg; Berlin, Heidelberg
- Resource Type
- Book chapter
- Language
- English
- Academic Unit
- Information Science
- Web of Science ID
- WOS:000238093200034
- Scopus ID
- 2-s2.0-33745523713
- Other Identifier
- 991019170120704721
InCites Highlights
Data related to this publication, from InCites Benchmarking & Analytics tool:
- Collaboration types
- Domestic collaboration
- International collaboration
- Web of Science research areas
- Computer Science, Information Systems
- Computer Science, Theory & Methods