On distributed information composition in big data systems

Haifa Alquwaiee, Songlin He, Chase Wu, Qiang Tang, Xuewen Shen

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Modern big data computing systems exemplified by Hadoop employ parallel processing based on distributed storage. The results produced by parallel tasks such as computing modules in scientific workflows or reducers in the MapReduce framework are typically stored in a distributed file system across multiple data nodes. However, most existing systems do not provide a mechanism to compose such distributed information, as required by many big data applications. We construct analytical cost models and formulate a Distributed Information Composition problem in Big Data Systems, referred to as DIC-BDS, to aggregate multiple datasets stored as data blocks in Hadoop Distributed File System (HDFS) using a composition operator of specific complexity to produce one final output. We rigorously prove that DIC-BDS is NP-complete, and propose two heuristic algorithms: Fixed-window Distributed Composition Scheme (FDCS) and Dynamic-window Distributed Composition Scheme with Delay (DDCS-D). We conduct extensive experiments in Google clouds with various composition operators of commonly considered degrees of complexity including O(n), O(n log n), and O(n2). Experimental results illustrate the performance superiority of the proposed solutions over existing methods. Specifically, FDCS outperforms all other algorithms in comparison with a composition operator of complexity O(n) or O(n log n), while DDCS-D achieves the minimum total composition time with a composition operator of complexity O(n2). These algorithms provide an additional level of data processing for efficient information aggregation in existing workflow and big data systems.

Original languageEnglish (US)
Title of host publicationProceedings - IEEE 15th International Conference on eScience, eScience 2019
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages168-177
Number of pages10
ISBN (Electronic)9781728124513
DOIs
StatePublished - Sep 2019
Event15th IEEE International Conference on eScience, eScience 2019 - San Diego, United States
Duration: Sep 24 2019Sep 27 2019

Publication series

NameProceedings - IEEE 15th International Conference on eScience, eScience 2019

Conference

Conference15th IEEE International Conference on eScience, eScience 2019
CountryUnited States
CitySan Diego
Period9/24/199/27/19

All Science Journal Classification (ASJC) codes

  • Computer Science Applications
  • Software
  • Ecological Modeling
  • Modeling and Simulation

Keywords

  • Big data
  • Distributed algorithms
  • Information composition
  • Task scheduling

Fingerprint Dive into the research topics of 'On distributed information composition in big data systems'. Together they form a unique fingerprint.

Cite this