Distributed and parallel construction method for equi-width histogram in cloud database

Article type: Research Article

Authors: Wang, Yang^{a; b} | Zhong, Yong^a | Ma, Qingshan^{a; b} | Yang, Guanci^{c; *}

Affiliations: [a] Chengdu Institute of Computer Applications, Chinese Academy of Sciences, Chengdu, Sichuan, China | [b] University of Chinese Academy of Sciences, Beijing, China | [c] Key Laboratory of Advanced Manufacturing Technology, Ministry of Education, Guizhou University, Guiyang, Guizhou, China

Correspondence: [*] Corresponding author: Guanci Yang, Key Laboratory of Advanced Manufacturing Technology, Ministry of Education, Guizhou University, Guiyang 550025, Guizhou, China. Tel.: +86 15180898460; E-mail: guanci_yang@163.com.

Abstract: Data distribution summary has been commonly used in databases to support query optimization, and histograms are of particular interest. A significant issue in histogram estimation is the large amount of data transmission. This paper presents a distributed and parallel construction method for equi-width histogram in cloud database (called DPHCD). Unlike previous methods, the DPHCD does not require the transfer of any table detail during histogram construction. Only small information about buckets and a few necessary data need to be transmitted over the network. The data transmission of DPHCD is unrelated with table size. DPHCD divides the histogram task into small tasks that could be simultaneously executed in a distributed cluster. It uses an innovative tablet-level sampling method to reduce the computing overhead in each cluster node. DPHCD is implemented in the Xugu cloud database management system. Experimental results demonstrate that DPHCD can achieve small data transmission and speed up histogram construction.

Keywords: Cloud database, equi-width histogram, distributed and parallel computing, data transmission

DOI: 10.3233/MGS-170273

Journal: Multiagent and Grid Systems, vol. 13, no. 3, pp. 311-329, 2017