Publication: Column-based partitioning for data in high dimensional space
Issued Date
2007-12-01
Resource Type
ISSN
01903918
Other identifier(s)
2-s2.0-47249131266
Rights
Mahidol University
Rights Holder(s)
SCOPUS
Bibliographic Citation
Proceedings of the International Conference on Parallel Processing. (2007)
Suggested Citation
Ekasit Kijsipongse, Sudsanguan Ngamsuriyaroj Column-based partitioning for data in high dimensional space. Proceedings of the International Conference on Parallel Processing. (2007). doi:10.1109/ICPP.2007.27 Retrieved from: https://repository.li.mahidol.ac.th/handle/20.500.14594/24383
Research Projects
Organizational Units
Authors
Journal Issue
Thesis
Title
Column-based partitioning for data in high dimensional space
Author(s)
Other Contributor(s)
Abstract
Several scientific applications such as 3D Jacobi Iteration [17] and LQCD [5] demand high computing power, and run on parallel systems. Such applications mostly operate on high dimensional data, and partitioning them into smaller units would help reduce their execution time considerably. Many algorithms such as CBP [2], Dissect [15], and Bisection [3] are proposed to find an optimal partitioning for two dimensional data. Simply extending such algorithms to handle higher dimensional data does not guarantee the maximum efficiency since the number of data dimensions must be taken into account. In addition, the communication cost among data in high dimensions is increased since data have high interaction to each other. This paper proposes a new algorithm called HyperCBP which is a general optimal column-based partitioning in high dimensional space. The algorithm divides high dimensional data into rectangle blocks of different sizes according to the computing power of each computing node, and minimizes the communication time used in transferring data among rectangles. We evaluate our algorithm using the new defined performance metric called Communication Saving Ratio (CSR). When compared with Dissect [15] and Bisection [3], the results show that HyperCBP gives a higher CSR than those two algorithms, and thus results in a better partitioning. © 2007 IEEE.