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

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)

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  -