ylfink@water.UUCP (05/20/87)
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.