Proceedings of the 2nd International Conference on Electronic & Mechanical Engineering and Information Technology (EMEIT 2012)

Research on optimization and parallelization of Optimal Binary Search Tree using Dynamic Programming

Authors
Bo Han, Yongquan Lu
Corresponding Author
Bo Han
Available Online September 2012.
DOI
10.2991/emeit.2012.45How to use a DOI?
Keywords
Dynamic Programming, Optimal Binary Search Tree, optimization, parallelization
Abstract

The classical algorithm uses Dynamic Programming to construct an Optimal Binary Search Tree. In this paper, we research into the dynamical process of building an Optimal Binary Search Tree and present an optimized solution. Time complexity is reduced from O (n3) to O (n2). Meanwhile, three feasible parallel solutions are put forward to achieve greater optimization. Some experiments on cluster have been done to compare efficiency of parallel and serial algorithm and the result shows that the parallel algorithm is much better. In the case of a larger amount of testing data, the parallel solution can save half of the time consumption. However, because of the particularity of this issue, the parallel algorithm has its own limitation.

Copyright
© 2012, the Authors. Published by Atlantis Press.
Open Access
This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Download article (PDF)

Volume Title
Proceedings of the 2nd International Conference on Electronic & Mechanical Engineering and Information Technology (EMEIT 2012)
Series
Advances in Intelligent Systems Research
Publication Date
September 2012
ISBN
10.2991/emeit.2012.45
ISSN
1951-6851
DOI
10.2991/emeit.2012.45How to use a DOI?
Copyright
© 2012, the Authors. Published by Atlantis Press.
Open Access
This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Cite this article

TY  - CONF
AU  - Bo Han
AU  - Yongquan Lu
PY  - 2012/09
DA  - 2012/09
TI  - Research on optimization and parallelization of Optimal Binary Search Tree using Dynamic Programming
BT  - Proceedings of the 2nd International Conference on Electronic & Mechanical Engineering and Information Technology (EMEIT 2012)
PB  - Atlantis Press
SP  - 229
EP  - 233
SN  - 1951-6851
UR  - https://doi.org/10.2991/emeit.2012.45
DO  - 10.2991/emeit.2012.45
ID  - Han2012/09
ER  -