{"id":13012,"date":"2021-12-02T20:46:59","date_gmt":"2021-12-03T01:46:59","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=13012"},"modified":"2026-06-02T14:59:24","modified_gmt":"2026-06-02T18:59:24","slug":"tr-99-09-load-balanced-and-communication-efficient-partitioning-strategies-for-parallel-data-cube-generation","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1999\/tr-99-09-load-balanced-and-communication-efficient-partitioning-strategies-for-parallel-data-cube-generation\/","title":{"rendered":"TR-99-09: Load Balanced and Communication Efficient Partitioning Strategies for Parallel Data Cube Generation"},"content":{"rendered":"\n
\n
\n\n
\n
\n
\n

\n TR-99-09: Load Balanced and Communication Efficient Partitioning Strategies for Parallel Data Cube Generation\n <\/h1>\n \n \n <\/header>\n\n <\/div>\n\n <\/div>\n\n <\/div>\n<\/section>\n\n

Carleton University
\nTechnical Report<\/a> TR-99-09
\nNovember 1999<\/p>\n\n\n\n

Load Balanced and Communication Efficient Partitioning Strategies for Parallel Data Cube Generation<\/h2>\n\n\n\n
\n
\n
\n
\n
\n
\n
\n
\n
Z. Chen, Frank Dehne, S. Hambrusch, A. Rau-Chaplin<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n
\n

Abstract<\/h3>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n\n\n\n

In this paper we present a general framework for the efficient parallelization of existing data cube construction algorithms. We present two different partitioning strategies, one for top-down and one for bottom-up cube algorithms. Both strategies balance the loads assigned to the processors and minimize communication overhead. Subcube computations are carried out using existing sequential, external memory data cube algorithms. The bottom-up partitioning strategy balances the number of single column external sorts made by each processor. The top-down strategy partitions a weighted tree in which weights reflect algorithm specific cost measures like estimated view sizes. Communication overhead is minimized by avoiding irregular and data-driven communication patterns, sending few large messages instead of many small ones, and overlapping communication and computation. Both partitioning approaches are architecture independent. They can be implemented on any parallel machines composed of processors connected via an interconnection fabric. Processors are assumed to have standard-size local memory and access to parallel disks. The interconnection fabric can be an interconnection network or shared memory. Experimental results presented support the claim that our partitioning strategies generate load balanced subcube problems requiring only small communication overhead. We measure the quality of a partitioning with respect to the sizes of the subproblems generated, the sequential time needed by each processor to perform the subcube computation, and the size of the output generated by each processor. We compare our results to optimal partitionings and to optimal parallel time.<\/p>\n\n\n\n

TR-99-09.pdf<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"

Carleton University Technical Report TR-99-09 November 1999 Load Balanced and Communication Efficient Partitioning Strategies for Parallel Data Cube Generation Z. Chen, Frank Dehne, S. Hambrusch, A. Rau-Chaplin Abstract In this paper we present a general framework for the efficient parallelization of existing data cube construction algorithms. We present two different partitioning strategies, one for top-down […]<\/p>\n","protected":false},"author":2,"featured_media":0,"parent":12244,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_acf_changed":false,"_cu_dining_location_slug":"","footnotes":"","_links_to":"","_links_to_target":""},"cu_page_type":[],"class_list":["post-13012","page","type-page","status-publish","hentry"],"acf":{"cu_post_thumbnail":false},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/13012","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/comments?post=13012"}],"version-history":[{"count":1,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/13012\/revisions"}],"predecessor-version":[{"id":13013,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/13012\/revisions\/13013"}],"up":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12244"}],"wp:attachment":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/media?parent=13012"}],"wp:term":[{"taxonomy":"cu_page_type","embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/cu_page_type?post=13012"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}