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.
Description
Keywords
Computer Science