Sage Journals: Discover world-class research

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

Get full access to this article

View all access options for this article.

References

Chang

Dean

Ghemawat

et al., Bigtable: A distributed storage system for structured data, Proceedings of the 7th Symposium on Operating System Design and Implementation, Seattle, Washington, USA (6–8 November 2006), 205–218.

Foundation Apache Software. https://en.wikipedia.org/wiki/Apache_HBase.

Lakshman

and Malik

, Cassandra: A decentralized structured storage system, ACM SIGOPS Operating Systems Review 44(2) (2010), 35–40.

Mongodb Inc. https://www.mongodb.com.

Redislabs. http://www.redis.io.

Corbett

J.C.

Dean

Epstein

et al., Spanner: Google’s globally distributed database, ACM Transactions on Computer Systems (TOCS) 31(3) (2013), 1–22.

Pokorný

, Database technologies in the world of big data, Proceedings of the 16th International Conference on Computer Systems and Technologies, Dublin, Ireland (25–26 June 2015), 1–12.

Weiss

, A technical overview of the Oracle Exadata database machine and exadata storage server, Oracle White Paper, Oracle Corporation, Redwood Shores (2012).

Cheng

C.X.

Song

X.M.

and Zhou

C.H.

, Generic cumulative annular bucket histogram for spatial selectivity estimation of spatial database management system, International Journal of Geographical Information Science 27(2) (2013), 339–362.

10.

Yıldız

Büyüktanır

and Emekci

, Equi-depth histogram construction for big data with quality guarantees, arXiv preprint, arXiv:1606.05633, 2016.

11.

MapR Technologies. https://mapr.com/blog/in-depth-look-hbase-architecture/.

12.

Ioannidis

, The history of histograms (abridged), Proceedings of the 29th International Conference on Very Large Data Bases, Berlin, Germany (9–12 September 2003), 19–30.

13.

Poosala

Haas

P.J.

Ioannidis

et al., Improved histograms for selectivity estimation of range predicates, SIGMOD ’96 Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data, Montreal, Quebec, Canada (4–6 June 1996), 294–305.

14.

Chaudhuri

Narasayya

and Motwani

, Random sampling for histogram construction: how much is enough? SIGMOD ’98 Proceedings of the 1998 ACM SIGMOD International Conference on Management of Data, Seattle, Washington, USA (1–4 June 1998), 436–447.

15.

Luo

J.Z.

and Wang

H.Z.

, Construction of an adaptive histogram in compressed database, Journal of Software 20(7) (2009), 1785–1799.

16.

Bruno

Chaudhuri

Gravano

et al., STHoles: A multidimensional workload-aware histogram, SIGMOD ’01 Proceedings of the 2001 ACM SIGMOD International Conference on Management of Data, Santa Barbara, California, USA (21–24 May 2001), 211–222.

17.

Kanne

C.C.

and Moerkotte

, Histograms reloaded: The merits of bucket diversity, SIGMOD ’10 Proceedings of the 2010 ACM SIGMOD International Conference on Management of Data, Indianapolis, Indiana, USA (6–10 June 2010), 663–674.

18.

Jestes

and Li

, Building wavelet histograms on large data in MapReduce, Proceedings of the Vldb Endowment 5(2) (2011), 109–120.

19.

Tang

M.W.

, Efficient and scalable monitoring and summarization of large probabilistic data, SIGMOD ’13 PhD Symposium Proceedings of the 2013 SIGMOD/PODS PhD Symposium, New York, USA (23–23 June 2013), 61–66.

20.

Zhang

C.C.

, Design and optimize big-data join algorithms using MapReduce, Unpublished PhD thesis, University of Science and Technology of China, Hefei, China, 2014.

21.

Shi

Y.J.

Meng

X.F.

Wang

F.S.

et al., HEDC+⁣+: An extended histogram estimator for data in the cloud, Journal of Computer Science and Technology 28(6) (2013), 973–988.

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

Abstract

Keywords

Get full access to this article

References