A new speculative execution algorithm based on C4.5 decision tree for Hadoop

Yuanzhen Li; Qun Yang; Shangqi Lai; Bohan Li

A new speculative execution algorithm based on C4.5 decision tree for Hadoop

Yuanzhen Li, Qun Yang, Shangqi Lai, Bohan Li

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

Abstract

As a distributed computing platform, Hadoop provides an effective way to handle big data. In Hadoop, the completion time of job will be delayed by a straggler. Although the definitive cause of the straggler is hard to detect, speculative execution is usually used for dealing with this problem, by simply backing up those stragglers on alternative nodes. In this paper, we design a new Speculative Execution algorithm based on C4.5 Decision Tree, SECDT, for Hadoop. In SECDT, we speculate completion time of stragglers and also of backup tasks, based on a kind of decision tree method: C4.5 decision tree. After we speculate the completion time, we compare the completion time of stragglers and of the backup tasks, calculating their differential value, and selecting the straggler with the maximum differential value to start the backup task. Experiment result shows that the SECDT can predict execution time more accurately than other speculative execution methods, hence reduce the job completion time.

Original language	English
Title of host publication	Intelligent Computation in Big Data Era - International Conference of Young Computer Scientists, Engineers and Educators, ICYCSEE 2015, Proceedings
Editors	Hongzhi Wang, Wanxiang Che, Zhaowen Qiu, Zhongyuan Han, Junyu Lin, Haoliang Qi, Zeguang Lin, Leilei Kong
Publisher	Springer
Pages	284-291
Number of pages	8
ISBN (Electronic)	9783662462478
Publication status	Published - 2015
Externally published	Yes
Event	International Conference of Young Computer Scientists, Engineers and Educators 2015 - Harbin, China Duration: 10 Jan 2015 → 12 Jan 2015 https://link.springer.com/book/10.1007/978-3-662-46248-5 (Proceedings)

Publication series

Name	IFIP Advances in Information and Communication Technology
Volume	503
ISSN (Print)	1868-4238

Conference

Conference	International Conference of Young Computer Scientists, Engineers and Educators 2015
Abbreviated title	ICYCSEE 2015
Country/Territory	China
City	Harbin
Period	10/01/15 → 12/01/15
Internet address	https://link.springer.com/book/10.1007/978-3-662-46248-5 (Proceedings)

Keywords

C4.5 decision tree
Hadoop
Speculative execution

Cite this

Li, Y., Yang, Q., Lai, S., & Li, B. (2015). A new speculative execution algorithm based on C4.5 decision tree for Hadoop. In H. Wang, W. Che, Z. Qiu, Z. Han, J. Lin, H. Qi, Z. Lin, & L. Kong (Eds.), Intelligent Computation in Big Data Era - International Conference of Young Computer Scientists, Engineers and Educators, ICYCSEE 2015, Proceedings (pp. 284-291). (IFIP Advances in Information and Communication Technology; Vol. 503). Springer.

Li, Yuanzhen ; Yang, Qun ; Lai, Shangqi et al. / A new speculative execution algorithm based on C4.5 decision tree for Hadoop. Intelligent Computation in Big Data Era - International Conference of Young Computer Scientists, Engineers and Educators, ICYCSEE 2015, Proceedings. editor / Hongzhi Wang ; Wanxiang Che ; Zhaowen Qiu ; Zhongyuan Han ; Junyu Lin ; Haoliang Qi ; Zeguang Lin ; Leilei Kong. Springer, 2015. pp. 284-291 (IFIP Advances in Information and Communication Technology).

@inproceedings{cc5450cf420f424ea8aeb03543b6eb01,

title = "A new speculative execution algorithm based on C4.5 decision tree for Hadoop",

abstract = "As a distributed computing platform, Hadoop provides an effective way to handle big data. In Hadoop, the completion time of job will be delayed by a straggler. Although the definitive cause of the straggler is hard to detect, speculative execution is usually used for dealing with this problem, by simply backing up those stragglers on alternative nodes. In this paper, we design a new Speculative Execution algorithm based on C4.5 Decision Tree, SECDT, for Hadoop. In SECDT, we speculate completion time of stragglers and also of backup tasks, based on a kind of decision tree method: C4.5 decision tree. After we speculate the completion time, we compare the completion time of stragglers and of the backup tasks, calculating their differential value, and selecting the straggler with the maximum differential value to start the backup task. Experiment result shows that the SECDT can predict execution time more accurately than other speculative execution methods, hence reduce the job completion time.",

keywords = "C4.5 decision tree, Hadoop, Speculative execution",

author = "Yuanzhen Li and Qun Yang and Shangqi Lai and Bohan Li",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2015. Copyright: Copyright 2015 Elsevier B.V., All rights reserved.; International Conference of Young Computer Scientists, Engineers and Educators 2015, ICYCSEE 2015 ; Conference date: 10-01-2015 Through 12-01-2015",

year = "2015",

language = "English",

series = "IFIP Advances in Information and Communication Technology",

publisher = "Springer",

pages = "284--291",

editor = "Hongzhi Wang and Wanxiang Che and Zhaowen Qiu and Zhongyuan Han and Junyu Lin and Haoliang Qi and Zeguang Lin and Leilei Kong",

booktitle = "Intelligent Computation in Big Data Era - International Conference of Young Computer Scientists, Engineers and Educators, ICYCSEE 2015, Proceedings",

address = "Switzerland",

url = "https://link.springer.com/book/10.1007/978-3-662-46248-5",

}

Li, Y, Yang, Q, Lai, S & Li, B 2015, A new speculative execution algorithm based on C4.5 decision tree for Hadoop. in H Wang, W Che, Z Qiu, Z Han, J Lin, H Qi, Z Lin & L Kong (eds), Intelligent Computation in Big Data Era - International Conference of Young Computer Scientists, Engineers and Educators, ICYCSEE 2015, Proceedings. IFIP Advances in Information and Communication Technology, vol. 503, Springer, pp. 284-291, International Conference of Young Computer Scientists, Engineers and Educators 2015, Harbin, China, 10/01/15.

A new speculative execution algorithm based on C4.5 decision tree for Hadoop. / Li, Yuanzhen; Yang, Qun; Lai, Shangqi et al.
Intelligent Computation in Big Data Era - International Conference of Young Computer Scientists, Engineers and Educators, ICYCSEE 2015, Proceedings. ed. / Hongzhi Wang; Wanxiang Che; Zhaowen Qiu; Zhongyuan Han; Junyu Lin; Haoliang Qi; Zeguang Lin; Leilei Kong. Springer, 2015. p. 284-291 (IFIP Advances in Information and Communication Technology; Vol. 503).

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › Research › peer-review

TY - GEN

T1 - A new speculative execution algorithm based on C4.5 decision tree for Hadoop

AU - Li, Yuanzhen

AU - Yang, Qun

AU - Lai, Shangqi

AU - Li, Bohan

PY - 2015

Y1 - 2015

N2 - As a distributed computing platform, Hadoop provides an effective way to handle big data. In Hadoop, the completion time of job will be delayed by a straggler. Although the definitive cause of the straggler is hard to detect, speculative execution is usually used for dealing with this problem, by simply backing up those stragglers on alternative nodes. In this paper, we design a new Speculative Execution algorithm based on C4.5 Decision Tree, SECDT, for Hadoop. In SECDT, we speculate completion time of stragglers and also of backup tasks, based on a kind of decision tree method: C4.5 decision tree. After we speculate the completion time, we compare the completion time of stragglers and of the backup tasks, calculating their differential value, and selecting the straggler with the maximum differential value to start the backup task. Experiment result shows that the SECDT can predict execution time more accurately than other speculative execution methods, hence reduce the job completion time.

AB - As a distributed computing platform, Hadoop provides an effective way to handle big data. In Hadoop, the completion time of job will be delayed by a straggler. Although the definitive cause of the straggler is hard to detect, speculative execution is usually used for dealing with this problem, by simply backing up those stragglers on alternative nodes. In this paper, we design a new Speculative Execution algorithm based on C4.5 Decision Tree, SECDT, for Hadoop. In SECDT, we speculate completion time of stragglers and also of backup tasks, based on a kind of decision tree method: C4.5 decision tree. After we speculate the completion time, we compare the completion time of stragglers and of the backup tasks, calculating their differential value, and selecting the straggler with the maximum differential value to start the backup task. Experiment result shows that the SECDT can predict execution time more accurately than other speculative execution methods, hence reduce the job completion time.

KW - C4.5 decision tree

KW - Hadoop

KW - Speculative execution

UR - https://www.scopus.com/pages/publications/84927699431

M3 - Conference Paper

AN - SCOPUS:84927699431

T3 - IFIP Advances in Information and Communication Technology

SP - 284

EP - 291

BT - Intelligent Computation in Big Data Era - International Conference of Young Computer Scientists, Engineers and Educators, ICYCSEE 2015, Proceedings

A2 - Wang, Hongzhi

A2 - Che, Wanxiang

A2 - Qiu, Zhaowen

A2 - Han, Zhongyuan

A2 - Lin, Junyu

A2 - Qi, Haoliang

A2 - Lin, Zeguang

A2 - Kong, Leilei

PB - Springer

T2 - International Conference of Young Computer Scientists, Engineers and Educators 2015

Y2 - 10 January 2015 through 12 January 2015

ER -

Li Y, Yang Q, Lai S, Li B. A new speculative execution algorithm based on C4.5 decision tree for Hadoop. In Wang H, Che W, Qiu Z, Han Z, Lin J, Qi H, Lin Z, Kong L, editors, Intelligent Computation in Big Data Era - International Conference of Young Computer Scientists, Engineers and Educators, ICYCSEE 2015, Proceedings. Springer. 2015. p. 284-291. (IFIP Advances in Information and Communication Technology).

A new speculative execution algorithm based on C4.5 decision tree for Hadoop

Abstract

Publication series

Conference

Keywords

Other files and links

Cite this