Max Planck Institute for Plasma Physics · 2004 · 10 citations · 0 references
ComputingComputer EngineeringComputer ScienceAlgorithmsComputer ArchitectureData StructuresData Structure AlgorithmsData Structure DesignHash TablesLookup TablesMemory HierarchySorting AlgorithmsSorting
Search tree data structures like van Emde Boas trees are a theoretically \nattractive alternative to comparison based search trees because they have \nbetter asymptotic performance for small integer keys and large inputs. This \npaper studies their practicability using 32 bit keys as an example. While \ndirect implementations of van Emde Boas trees cannot compete with good \nimplementations of comparison based data structures, our tuned data structure \nsignificantly outperforms comparison based implementations for searching and \nshows at least comparable performance for insertion and deletion.