phyllis@utcsrgv.UUCP (Phyllis Eve Bregman) (10/18/83)
***NOTE DAY AND PLACE CHANGES***
Wednesday, October 19th, 2:00 P.M., GB305: Prof. Markuu Tamminen,
Helsinki University of Technology, Laboratory of Information Processing
Science, Helsinki, Finland: "On search by address computation".
ABSTRACT: We study the effect of data distribution on the efficiency
of address computation data structures for searching, as typified by
the priority queue problem. We present a comparison of several different
techniques and show that, in contrast to sorting, neither one nor
multilevel bucket methods are uniformly efficient for the above task.
As a remedy we propose an enhancement of order preserving extendible
hashing. This structure is shown to behave asymptotically independently
of the amount of data and its distribution. From the one-dimensional
analysis we draw conclusions regarding multi-attribute file structures.
--
Phyllis Eve Bregman
CSRG, Univ. of Toronto
{decvax,linus,ihnp4,uw-beaver,floyd,utzoo}!utcsrgv!phyllis