gh@utai.UUCP (Graeme Hirst) (10/25/84)
COLLOQUIUM
Department of Computer Science, University of Toronto
11:00, Tuesday 30 October 1984, Sandford Fleming 1105
Helping the Lost and Confused:
Computer Retrieval of Books and Maps
Michael Lesk
Bell Communications Research
Murray Hill, NJ
What good does it do to have lots of information in
machine-readable form if you can't access it? Two experi-
ments addressing this issue will be discussed. In one, Mur-
ray Hill library users chose between a keyword and menu user
interface to an on-line catalog, and in the other people got
driving directions from a computer.
(1) For two years, the Murray Hill library has had an
on-line public catalog, which was installed to see whether
the customers would prefer a keyword retrieval system, in
which they type author names, subject words, etc., or a menu
system, in which they chose subject categories from the
Dewey hierarchy. Conventional wisdom (e.g., in the design
of Prestel) is that users would rather choose from alterna-
tives, not name things. Our naive library users, contrary
to the literature recommendations, preferred the keyword
search system. We suggest deep menus are not appropriate
when users already have a good idea what they want.
(2) A machine-readable street map was the basis of the
second experiment, an attempt to give computerized driving
directions. This combined an interesting theoretical prob-
lem (shortest path in a graph), an interesting database
problem (storing a planar graph of 100,000 nodes and 150,000
edges, with fast retrieval needed by edge name, node loca-
tion, and connectivity), and a chance to be energy-efficient
(4% of the gasoline used in the UK is wasted, either by
drivers who are totally lost or just taking an inefficient
route). We investigated various search algorithms for find-
ing map routes, including breadth-first and depth-first
search. Either distance or time can be minimized. We've
found that merely shortest distance produces complex and
inappropriate routes; at least there must be a charge for
making turns. Two-directional depth-first search was gen-
erally good, but it's not what people use: they employ a
variant of divide-and-conquer.
--
\\\\ Graeme Hirst University of Toronto Computer Science Department
//// utcsrgv!utai!gh / gh.toronto@csnet-relay / 416-978-8747