Access Restriction

Author Nash, Nicholas ♦ Gregg, David
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2011
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Computer programming, programs & data
Subject Keyword Integer keys ♦ Level compression ♦ Searching ♦ Trees ♦ Tries
Abstract In this article, we experimentally compare a number of data structures operating over keys that are 32- and 64-bit integers. We examine traditional comparison-based search trees as well as data structures that take advantage of the fact that the keys are integers such as van Emde Boas trees and various trie-based data structures. We propose a variant of a burst trie that performs better in time than all the alternative data structures. In addition, even for small sets of keys, this burst trie variant occupies less space than comparison-based data structures such as red-black trees and $\textit{B}-trees.$ Burst tries have previously been shown to provide a very efficient base for implementing cache efficient string sorting algorithms. We find that with suitable engineering, they also perform excellently as a dynamic ordered data structure operating over integer keys. We provide experimental results when the data structures operate over uniform random data. We also present experimental results for other types of data, including datasets arising from $\textit{Valgrind},$ a widely used suite of tools for the dynamic binary instrumentation of programs.
ISSN 10846654
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2010-03-01
Publisher Place New York
e-ISSN 10846654
Journal Journal of Experimental Algorithmics (JEA)
Volume Number 15
Page Count 43
Starting Page 2.1
Ending Page 2.43

Open content in new tab

   Open content in new tab
Source: ACM Digital Library