Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!water!ylfink
From: ylfink@water.UUCP
Newsgroups: ont.events,uw.talks
Subject: Efficient Representation of Search Information & of Synthetic Pictures.
Message-ID: <956@water.UUCP>
Date: Wed, 20-May-87 13:33:36 EDT
Article-I.D.: water.956
Posted: Wed May 20 13:33:36 1987
Date-Received: Thu, 21-May-87 01:59:02 EDT
Distribution: ont
Organization: U of Waterloo, Ontario
Lines: 41
Keywords: CS, U of W, Prof. W. de Jonge, Fri., May 22/87, 1:30PM, MC 6091A.
Xref: utgpu ont.events:693 junk:5131



DEPARTMENT OF COMPUTER SCIENCE
UNIVERSITY OF WATERLOO
SEMINAR ACTIVITIES

DATA STRUCTURING SEMINAR

                    -  Friday, May 22, 1987

Professor  Wiebren  de Jonge of Vrije Universiteit, The
Netherlands,  will  speak on ``Efficient Representation
of Search Information and of Synthetic Pictures''.

TIME:                1:30 PM

ROOM:              MC 6091A

ABSTRACT

It  is  shown  how  a  highly compact representation of
binary  trees  can  be  used as the basis of two access
methods   for   dynamic  files,  called  BDS-trees  and
S-trees, respectively.

Both  these  methods  preserve key-order and offer easy
and  efficient sequential access. They are different in
the   way   the  compact  binary  trees  are  used  for
searching.  With  a  BDS-tree  the  search is a digital
search using binary digits.  Although the S-tree search
is  performed  on  a  bit-by-bit basis as well, it will
appear   to  be  slightly  different.   Actually,  with
S-trees  the compact binary trees are used to represent
separators  at low storage costs. As a result, the fan-
out,  and thus performance, of a B-tree can be improved
by   using   within  each  index  page  an  S-tree  for
representing separators efficiently.

The  techniques presented can also be used to represent
quad-trees  (which  are used e.g. for storing pictures)
more efficiently than with current methods.