Designing storage efficient decision trees

IEEE Transactions on ComputersPublished 1 March 1991

Owen Murphy, R.L. McCraw

DOI10.1109/12.76408

Source URL

Citations40

SJR quartileQ1

SJR score1.16

SNIP1.61

TL;DR

It is shown that for most cases, the construction of the storage optimal decision tree is an NP-complete problem, and therefore a heuristic approach to the problem is necessary.

Abstract

The problem of designing storage-efficient decision trees from decision tables is examined. It is shown that for most cases, the construction of the storage optimal decision tree is an NP-complete problem, and therefore a heuristic approach to the problem is necessary. A systematic procedure analogous to the information-theoretic heuristic is developed. The algorithm has low computational complexity and performs well experimentally.>

Keywords

Computer ScienceEngineering

Information Processing LettersConstructing optimal binary decision trees is NP-complete

956 Citations1976Laurent Hyafil, Ronald L. Rivest

The proof to be given is relatively simple and the importance of this result can be measured in terms of the Jarge amount of effort that has been put into fmding efftient aJgorJthms for constructing optimal binary decision trees.

ACM Computing SurveysDecision Trees and Diagrams

331 Citations1982Bernard M. E. Moret

In this tutorial survey a common framework of defimtmns and notation is established, the contributions from the main fields of apphcatmn are reviewed, recent results and extensions are presented, and areas of ongoing and future research are discussed.

View PDF

IEEE Transactions on Information TheoryApplication of information theory to the construction of efficient decision trees

104 Citations1982C. Hartmann, Pramod K. Varshney +2 more

This heuristic approach to the problem of conversion of decision tables to decision trees is treated and has low design complexity and yet provides near-optimal decision trees.

Journal of the Royal Statistical Society Series A (General)Identification Keys and Diagnostic Tables: A Review

72 Citations1980R. W. Payne, D. A. Preece

The paper attempts a synthesis of a large and widely dispersed literature that is not properly integrated, in that workers in one field of application have often been unaware of relevant theory developed in other fields.

Communications of the ACMConversion of limited-entry decision tables to computer programs

61 Citations1965Solomon L. Pollack

Two algorithms, based on work done by M. S. Montalbano, are extended here to handle dashes and ELSEm rules and minimizes the computer storage required for the resultant program.

View PDF

Journal of the ACMThe Complexity of Trie Index Construction

56 Citations1977Douglas E. Comer, Ravi Sethi

View PDF

Journal of the ACMConversion of Limited-Entry Decision Tables to Optimal Computer Programs II

36 Citations1967Lewis T. Reinwald, Richard M. Soland

The algorithm is initially developed for computer programs possessing a treelike form and then extended to a wider class of programs to find an equivalent computer program which minimizes a cost function which is nondecreasing in both average processing time and total storage requirement.

View PDF

Communications of the ACMConversion of decision tables to computer programs

34 Citations1965Laurence I. Press

Several translation procedures for the conversion of decision tables to programs are presented and then evaluated in terms of storage requirements, execution time and compile time.

View PDF