Theory for hierarchical menu structure optimization

The paper presents a formal model for hierarchical menu structure optimization. Each menu item is endowed with a probability of selection, and a discrete optimization problem is solved by choosing a menu hierarchy that minimizes the average search time. Categories in the optimal menu are proved to contain the same number of alternatives with the same relative popularity. The model covers the great variety of menu types and allows choosing the best type to meet the requirements of specific application or user category. We also suggest an automated routine for menu structure optimization that accounts for both semantic constraints and results of optimization, and illustrate it by optimizing a command menu of a mobile phone.