Back to Eric's Home Page Up to Site Map $Date: 1998/05/27 00:53:49 $

Key Trees -- Unified Searching and Browsing

This is a proposal for a unified searching/browsing model for the Trove project. This model was motivated by a desire to structure the controlled-keyword set so the user doesn't have to see all of it while specifying a package (that is, some keywords become `visible' only after given other keywords have been chosen).

Note: in developing this model I have deliberately avoided thinking about specific user interfaces or the HTML implementation problems thereof.

Specifications, Packages, and Searches

The general model is that the set of controlled keywords is structured like the nodes of a tree (or more generally like a directed acyclic graph). A keyword is selectable only when a predecessor node has been selected. A specification is a rooted path in the tree (e.g. a sequence of keywords going from root to most specific).

Each package has a list of specifications associated with it. A package matches a given specification if the package has some specification of which the given specification is a prefix. (Thus, if a package has the specification /a/b/c/d, any of the given specifications /a, /a/b, /a/b/c, or /a/b/c/d will match it.)

A search is a set of specifications created by the user. The result of the search is the intersection set of all packages that match every specification in the search.

An Example

As an example for this model, consider a user wishing to explore what graphics viewers are available in a Trove catalog. The user would like to be able to specify both (a) graphics formats of interest, and (b) a display toolkit (SVGA, Xlib, Motif, etc.). Let us suppose that the user is looking for a Motif GIF viewer.

The user's search might be performed by building the following pair of specifications: /topic/graphics/viewers/gif and /interface/toolkit/motif.

Catalogs and Browsing

A search defines a catalog, its result set. This model unifies searching and browsing; one browses the set of Trove packages by editing a collection of selections, and viewing the catalog resulting after each edit.

Sketch of Interface Design

The user is initially presented with a menu consisting of all keywords that appear in the leftmost slot of any spec. (This is a subset of the keytree nodes adjacent to root.)

On choosing one of these, the user is presented with all keywords which appear in slot 2 of a spec containing the chosen keyword in slot 1. This is browsing down the specs. In addition, any package tagged by a spec consisting solely of the chosen keyword is also displayed. There is also the further option Narrow Search.

Further choices of keywords walk down the spec path, displaying any packages that have been tagged by the currently chosen spec, along with the keywords for the next level. Eventually one reaches a level where there are only packages and no further keywords.

Choosing ``Narrow Search'' returns one to the top level, but now only those keywords and packages that can be located in the catalog consisting of the result of the previous browsing operation are selectable. Packages outside the catalog are ignored; excluded keywords are indicated in a non-selectable mode.

The purpose of `graying out' keywords is to allow the user to see instantly that what is wanted is inconsistent with the currently narrowed search. Narrowing can be iterated, or it can be backed out of (by throwing away rightmost segments of the current spec). At all times the current narrowing list and the current spec are displayed, so that the user doesn't get lost.

In this style, the user can hardly tell the difference between browsing and searching: ideally the delay is always the same, so one does not assemble a ``search string'' and then hit ``Search''; instead, one simply browses and, if the current catalog seems to be too large, narrows. Depending on external considerations, a too-large catalog might elicit a warning such as ``There are 3500 packages available. You can |display| the full list or |narrow| your search.'' (where pipe bars bracket hotlinks).

Sample Session

Let's say the top-level screen provides keywords Topic, Interface, Audience, Status, etc. (I will use This Style or THIS STYLE for keywords, and all-lower-case-nn.nn for packages.)

Choosing Topic, the user is presented with Compilers, Browsers, Graphics, etc. and Narrow Search (henceforth N.S.).

Choosing Graphics, the user is presented with Painters, Drawers, Viewers, etc. and N.S.

Choosing Viewers, the user is presented with GIF, JPEG, PNG, etc. the packages barfoo-2.2, zambaz-3.3 (these are packages that are not specialized as to format), and N.S.

Choosing GIF, the user gets packages foobar-1.2, bazzam-3.4, etc., etc., etc. and N.S. There are too many to investigate in detail, so the user chooses N.S. and is returned to the top level.

Choosing Interface, the user is presented with Dumb, Curses, Toolkit, etc.

Choosing Toolkit, the user is presented with razbaz-9.99 (which uses a standardly available toolkit), Motif, KDE, etc.

Choosing Motif, the user sees only foobar-1.2, the intersection of /Topic/Graphics/Viewers/GIF and /Interface/Toolkit/Motif.

And chooses it.

All of this can be done HTML-style, or using one or more choice boxes, or in any number of other ways - this is an abstract UI.

Back to Eric's Home Page Up to Site Map $Date: 1998/05/27 00:53:49 $

Eric S. Raymond <esr@snark.thyrsus.com>