Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.1 6/24/83; site watmath.UUCP
Path: utzoo!watmath!mwang
From: mwang@watmath.UUCP (mwang)
Newsgroups: ont.events
Subject: UW Data Structures Seminar, Dr. Tamminen on "On Search Address Computation"
Message-ID: <5994@watmath.UUCP>
Date: Tue, 18-Oct-83 13:44:17 EDT
Article-I.D.: watmath.5994
Posted: Tue Oct 18 13:44:17 1983
Date-Received: Thu, 20-Oct-83 00:19:15 EDT
Expires: Tue, 25-Oct-83 00:00:00 EDT
Organization: U of Waterloo, Ontario
Lines: 32


     _D_E_P_A_R_T_M_E_N_T _O_F _C_O_M_P_U_T_E_R _S_C_I_E_N_C_E
     _U_N_I_V_E_R_S_I_T_Y _O_F _W_A_T_E_R_L_O_O
     _S_E_M_I_N_A_R _A_C_T_I_V_I_T_I_E_S

     _D_A_T_A _S_T_R_U_C_T_U_R_E_S _S_E_M_I_N_A_R
                                - Monday, October 24, 1983.

     Dr. M. Tamminen of Helsinki  University  of  Technology
     will speak on ``On Search by Address Computation.''

     TIME:                10:30 AM  (Please Note)

     ROOM:              MC 5158

     ABSTRACT

     We study the effect of data distribution on  the  effi-
     ciency  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 mul-
     tiattribute file structures.

                      October 17, 1983