Computer Science – Performance
Scientific paper
2006-11-09
Computer Science
Performance
5 pages, 2 illustrations; conference version of cs.PF/0604016, accepted to ISIT 2007
Scientific paper
The decision tree is one of the most fundamental programming abstractions. A commonly used type of decision tree is the alphabetic binary tree, which uses (without loss of generality) ``less than'' versus ''greater than or equal to'' tests in order to determine one of $n$ outcome events. The process of finding an optimal alphabetic binary tree for a known probability distribution on outcome events usually has the underlying assumption that the cost (time) per decision is uniform and thus independent of the outcome of the decision. This assumption, however, is incorrect in the case of software to be optimized for a given microprocessor, e.g., in compiling switch statements or in fine-tuning program bottlenecks. The operation of the microprocessor generally means that the cost for the more likely decision outcome can or will be less -- often far less -- than the less likely decision outcome. Here we formulate a variety of $O(n^3)$-time $O(n^2)$-space dynamic programming algorithms to solve such optimal binary decision tree problems, optimizing for the behavior of processors with predictive branch capabilities, both static and dynamic. In the static case, we use existing results to arrive at entropy-based performance bounds. Solutions to this formulation are often faster in practice than ``optimal'' decision trees as formulated in the literature, and, for small problems, are easily worth the extra complexity in finding the better solution. This can be applied in fast implementation of decoding Huffman codes.
No associations
LandOfFree
On Conditional Branches in Optimal Decision Trees does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On Conditional Branches in Optimal Decision Trees, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Conditional Branches in Optimal Decision Trees will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-407684