MPI-INF Logo
Campus Event Calendar

Event Entry

What and Who

A Sorted List Data Structure for 32 Bit Keys

Roman Dementiev
Max-Planck-Institut für Informatik - AG 1
AG1 Mittagsseminar (own work)
AG 1  
AG Audience
English

Date, Time and Location

Wednesday, 7 January 2004
13:30
30 Minutes
46.1 - MPII
024
Saarbrücken

Contact

Roman Dementiev
122
--email hidden
passcode not visible
logged in users only

Tags, Category, Keywords and additional notes

Search tree data structures like van Emde Boas (vEB) trees

are a theoretically attractive alternative to comparison
based search trees because they have better asymptotic performance for small integer keys and large inputs.
This paper studies their practicability using 32 bit keys
as an example.While direct implementations of vEB-trees cannot compete with good implementations of comparison based data structures,our tuned data structure significantly outperforms comparison based implementations for searching and shows at least comparable performance for insertion and deletion.


Roman Dementiev, 12/30/2003 16:58 -- Created document.