Please use this identifier to cite or link to this item: http://hdl.handle.net/1880/46122
Title: ON FREQUENCY-BASED MENU-SPLITTING ALGORITHMS
Authors: Witten, Ian H.
Cleary, John G.
Keywords: Computer Science
Issue Date: 1-Jan-1983
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.
URI: http://hdl.handle.net/1880/46122
Appears in Collections:Witten, Ian
Cleary, John

Files in This Item:
There are no files associated with this item.


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.