On frequency-based menu-splitting algorithms

✍ Scribed by Ian H. Witten; John G. Cleary; Saul Greenberg

• Publisher: Elsevier Science
• Year: 1984
• Weight: 672 KB
• Volume: 21
• Category: Article
• ISSN: 0020-7373
• DOI: 10.1016/s0020-7373(84)80063-2

✦ Synopsis

If a menu-driven display is to be device-independent, the storage of information must be separated from its presentation by creating menus dynamically. As a first step, this article evaluates menu-construction algorithms for ordered directories whose access profile is specified. The algorithms are evaluated by the average number of selections required to retrieve items. While it is by no means suggested that the system designer should ignore other relevant information (natural groupings of menu items, context in terms of prior selections, and so on), the average selection count provides an unambiguous quantitative criterion by which to evaluate the performance of menu-construction algorithms.

Even in this tightly-circumscribed situation, optimal menu construction is surprisingly difficult. If the directory entries are accessed uniformly, theoretical 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 beeh 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.