Dichotomous Key Storage and Reduction


Aditi R. Oza

Oral Defence Date: 

Wednesday, April 23, 2008 - 17:30


TH 935


5:30 PM


Professor Murphy and Professor Yang


Botanists use a dichotomous key for plant identification in the field. Dichotomous keys are used to distinguish different groups of objects (plants) based on their observable properties. Dichotomous keys are in the form of directed acyclic graphs, with the different plants as the leaf (sink) nodes and decision nodes as the internal nodes. Each decision node contains two questions based on the observable properties of the plants. By selecting one option at each decision node, the plant is identified after a root-leaf traversal of the dichotomous key. It is possible to specialize a dichotomous key to distinguish any subset of plants in the original key by removing unnecessary decision nodes, a process we call key reduction. The unnecessary decision nodes are questions that do not require the user’s answer for accurate identification of plants within the subset, and that can be omitted. This allows the user to reach any of the plants of interest by answering a smaller number of intermediate questions. The major contribution of this work is design and verification of the key reduction algorithm. This algorithm has been implemented in a prototype system and behaves as expected. Dichotomous key storage in the prototype is based on a database schema that is well formed and normalized with complete integrity constraints. Applications of this new algorithm include efficient and straightforward reduction of dichotomous keys (e.g. for field work using low-end PDA’s or generation of reduced dichotomous keys for specific locations).

Aditi R. Oza

Dichotomous key, directed acyclic graph reduction algorithm