@inproceedings{39cd579d0b724a81a7fa22adddb87723,
title = "Communication and memory optimal parallel data cube construction",
abstract = "Data cube construction is a commonly used operation in data warehouses. Because of the volume of data that is stored and analyzed in a data warehouse and the amount of computation involved in data cube construction, it is natural to consider parallel machines for this operation. We address a number of algorithmic issues in parallel data cube construction. First, we present an aggregation tree for sequential (and parallel) data cube construction, which has minimally bounded memory requirements. An aggregation tree is parameterized by the ordering of dimensions. We present a parallel algorithm based upon the aggregation tree. We analyze the interprocessor communication volume and construct a closed form expression for it. We prove that the same ordering of the dimensions minimizes both the computational and communication requirements. We also describe a method for partitioning the initial array and prove that it minimizes the communication volume. Experimental results from implementation of our algorithms on a cluster of workstations validate our theoretical results.",
keywords = "Aggregates, Clustering algorithms, Companies, Concurrent computing, Data analysis, Data warehouses, Parallel algorithms, Parallel machines, Partitioning algorithms, Performance analysis",
author = "Ruoming Jin and Ge Yang and K. Vaidyanathan and G. Agrawal",
note = "Publisher Copyright: {\textcopyright} 2003 IEEE.; 2003 International Conference on Parallel Processing, ICPP 2003 ; Conference date: 06-10-2003 Through 09-10-2003",
year = "2003",
doi = "10.1109/TPDS.2005.144",
language = "English (US)",
volume = "16",
series = "Proceedings of the International Conference on Parallel Processing",
publisher = "Institute of Electrical and Electronics Engineers Inc.",
pages = "573--580",
editor = "P. Sadayappan and Chu-Sing Yang",
booktitle = "Proceedings - 2003 International Conference on Parallel Processing, ICPP 2003",
edition = "12",
}