phyllis@utcsrgv.UUCP (Phyllis Eve Bregman) (03/03/84)
UofT Department of Computer Science Seminar Schedule for
the week of March 5th, 1984
Monday, March 5th, 2:00 P.M., SF1105: Professor Bernard Chazelle
Department of Computer Science, Brown University, Providence,
Rhode Island: "Filtering search: A new approach to query-answering".
ABSTRACT: We introduce a new technique for solving problems of
the following form: preprocess a set of objects so that those
satisfying a given property with respect to a query object can
be listed effectively. Among well-known problems to fall into this
category we find range query, point enclosure, intersection,
near-neighbor problems, etc. The approach which we take is very
general and rests on a new concept called filtering search. We show
on a number of examples how it can be used to improve the complexity
of known algorithms and simplify their implementations as well.
In particular, filtering search allows us to improve on the
worst-case complexity of the best algorithms known so far for solving
the problems mentioned above.
--
Phyllis Eve Bregman
CSRG, Univ. of Toronto
{decvax,linus,ihnp4,uw-beaver,allegra,utzoo}!utcsrgv!phyllis
CSNET: phyllis@toronto
(416) 978 6985