Figure 2: Names++ application. In this picture, the user has tapped on the word "City" and opened a menu of recently used city names. If the user chooses one of these cities, it will be copied into the City field for this name. Compare this to Figure 1. Note that Names++ includes all features of Names relevant to adding a new name.
Two of Names' fields already had a menu. The Honorific field offered the user "Ms.", "Mrs.", "Mr.", and "Dr."; the Country field offered a menu of thirteen countries. For completeness, Names++ prepends the four most recent values to these fields' menus. Technically these are split menus. [Footnote: Not to be confused with splitting menu choices across multiple menus in (Witten, Cleary, & Greenberg, 1984).] Mitchell and Shneiderman (1989) compared large statically ordered menus (unsplit) to those that also prepended most-recently-used choices (split, exactly our condition). Static were faster than split menus on one task; there was no difference on another. Sears and Shneiderman (1994) later found evidence in favor of split menus including a 17-58% improvement in selection time compared to unsplit menus. They also compared alternative organizations for the split part and recommend limiting the number of split choices to four or less (which Names++ does) and sorting split choices by frequency (which Names++ approximates by most-recently-used). In the context of menu hierarchies, Snowberry, Parkinson, and Sisson (1985) found that adding items containing upcoming selections resulted in greater accuracy and faster search times. This result has not been confirmed (Kreigh, Pesot, and Halcomb, 1990) and may be as much an effect of preventing users from getting lost in menu hierarchies as of assisting them in making selections per se. We test adaptive (split) menus in Names++ to understand the relative contribution of such compared to other interfaces in a data entry task.
The four Phone Number fields have menus, but these give the user a way to categorize the phone number rather than enter the number itself. They are category menus (Norman, 1991). The phone menus include choices for "Phone", "Home", "Work", "Fax", "Car", "Beeper", "Mobile", and "Other". All phone fields have identical menus. Names++ does not modify them. No menus were provided for the First Name, Last Name, and Birthday fields. Section 5 describes which input fields should have menus.
To understand the computational space and time demands of adaptive menus, note that Names++ stores all menus in a single object in its own object database. The size of the object is linear in the number of fields with menus (f) and in the number of choices in each menu (c), or fc. If each menu were implemented as a circular queue, the time to update the object would be constant for each menu, or just f. Names++ uses a slightly slower array implementation for menus and takes fc time. In practice this works out to slightly more than one half second for nine fields and four choices.
Figure 3: Names++ application after the user adds a company for a new name. In the left panel, the application finds a previous name with a matching company, displays a dialog, and fills remaining fields with predicted information copied from the previous name. The center panel shows how much information was filled. The right panel shows the completed name. In this example the user has written only four additional words to complete the name.
Names++ behaves similarly when the user adds a city or state that matches a previous name, but it copies over less information than when a matching company is found. If a value copied by predictive fillin is incorrect, the user can write or choose the correct value manually. Table 1 summarizes which fields have menus and predictive fillin. The structure of predictive fillin is fixed in the design of Names++. Other work attempts to learn comparable structure from examples (e.g., Dent et al., 1992; Hermens & Schlimmer, 1994; Schlimmer & Hermens, 1993; Yoshida, 1994). Our goal is to determine whether the end result of such learning is worthwhile.
Table 1: Name++ fields with adaptive menus and predictive fillin.
If more than one previous name matches the company, city, or state of the new name, Names++ fills fields with values from the most recent name. Values from the second-most recent occurrence of that name are added to menus. This gives the user a chance to select between alternate addresses for the same company or alternate zip codes for the same city.
In terms of computational requirements, Names++ needs no additional storage for predictive fillin; the object database of previously added names is reused as a case base. Matching a new name's company, city, or state to a previous name is implemented with a Newton primitive; an informal study depicted in Figure 4 indicates that Newton's proprietary algorithm appears to run in time linear in the number of names if no match is found and logarithmic if matches are found.
Figure 4: Time to find a matching name using Newton as a function of the number of names in the database if no match exists (circles and upper line) and if several matches exist (squares and lower line). Both axes are linear scale. The upper line is a linear fit; the lower line is logarithmic. For comparison to the experiment, interpolated values for 200 names are shown with open symbols.
Names++ and its source code is in on-line Appendix A.