MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Dementiev, Roman
Kettner, Lutz
Mehnert, Jens
Sanders, Peter
dblp
dblp
dblp
dblp
Editor(s):
Arge, Lars
Italiano, Giuseppe F.
Sedgewick, Robert
dblp
dblp
dblp
Not MPII Editor(s):
Arge, Lars
Italiano, Giuseppe F.
Sedgewick, Robert
BibTeX cite key*:
Dementiev2004SearchTree
Title, Booktitle
Title*:
Engineering a Sorted List Data Structure for 32 Bit Key
Booktitle*:
Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algorithmics and Combinatorics (ALENEX-04)
Event, URLs
Conference URL::
http://www.siam.org/meetings/alenex04/index.htm
Downloading URL:
Event Address*:
New Orleans, LA, USA
Language:
English
Event Date*
(no longer used):
Organization:
Event Start Date:
24 January 2005
Event End Date:
24 January 2005
Publisher
Name*:
SIAM
URL:
http://www.siam.org/
Address*:
Philadelphia, USA
Type:
Vol, No, Year, pp.
Series:
Volume:
Number:
Month:
January
Pages:
142-151
Year*:
2004
VG Wort Pages:
28
ISBN/ISSN:
0-89871-564-4
Sequence Number:
DOI:
Note, Abstract, ©
(LaTeX) Abstract:
Search tree data structures like van Emde Boas 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 van Emde Boas 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.
URL for the Abstract:
http://www.mpi-sb.mpg.de/~kettner/pub/veb_tree_alenex_04_a.html
Keywords:
Data Structures
HyperLinks / References / URLs:
http://www.mpi-sb.mpg.de/~kettner/proj/veb/index.html
Download
Access Level:
Public

Correlation
MPG Unit:
Max-Planck-Institut für Informatik
MPG Subunit:
Algorithms and Complexity Group
Appearance:
MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort



BibTeX Entry:

@INPROCEEDINGS{Dementiev2004SearchTree,
AUTHOR = {Dementiev, Roman and Kettner, Lutz and Mehnert, Jens and Sanders, Peter},
EDITOR = {Arge, Lars and Italiano, Giuseppe F. and Sedgewick, Robert},
TITLE = {Engineering a Sorted List Data Structure for 32 Bit Key},
BOOKTITLE = {Proceedings of the Sixth Workshop on Algorithm Engineering and Experiments and the First Workshop on Analytic Algorithmics and Combinatorics (ALENEX-04)},
PUBLISHER = {SIAM},
YEAR = {2004},
PAGES = {142--151},
ADDRESS = {New Orleans, LA, USA},
MONTH = {January},
ISBN = {0-89871-564-4},
}


Entry last modified by Christine Kiesel, 05/23/2005
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Lutz Kettner
Created
01/24/2005 11:31:37 AM
Revisions
6.
5.
4.
3.
2.
Editor(s)
Christine Kiesel
Lutz Kettner
Ulrich Meyer
Sabine Krott
Sabine Krott
Edit Dates
23.05.2005 15:11:25
05/20/2005 02:40:56 PM
04/20/2005 05:15:49 PM
02.02.2005 13:47:35
02.02.2005 10:46:27