Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84; site utai.UUCP
Path: utzoo!utcsrgv!utai!gh
From: gh@utai.UUCP (Graeme Hirst)
Newsgroups: ont.events
Subject: U of T Colloquium: Mike Lesk, Tuesday 30 Oct
Message-ID: <267@utai.UUCP>
Date: Thu, 25-Oct-84 11:18:03 EDT
Article-I.D.: utai.267
Posted: Thu Oct 25 11:18:03 1984
Date-Received: Thu, 25-Oct-84 22:04:17 EDT
Distribution: ont
Organization: CSRI, University of Toronto
Lines: 52

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