mwang@watmath.UUCP (mwang) (10/18/83)
_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