ON FREQUENCY-BASED MENU-SPLITTING ALGORITHMS

Abstract

If a menu-driven display is to be device independent, the storage of information must be separated from its presentation by creating menus dynamically. This contrasts with current public information systems, which store menus as literal text and are thereby committed to particular display formats. As a first step towards device-independent menu display, we have investigated menu-construction algorithms for accessing items from an ordered dictionary whose frequency profile of access is specified. We aim to minimize the average number of selections required to retrieve an item. Even in this simple situation, optimal menu construction is surprisingly difficult. If the dictionary entries are accessed uniformly, theorectical analysis leads to a selection algorithm different from the obvious one of splitting ranges into approximately equal parts at each stage. Analysis is intractable for other distributions, although the performance of menu-splitting algorithms can be bounded. The optimal menu tree can be found by searching, but this is computationally infeasible for any but the smallest problems. Several practical algorithms, which differ in their treatment of rounding in the menu-splitting process and lead in general to quite different menu trees, have been investigated by computer simulation with a Zipf distribution access profile. Surprisingly, their performance is remarkably similar. However, our limited experience with optimal menu trees suggests that these algorithms leave some room for improvement.