%0 Book Section
%B Experimental Algorithms
%D 2007
%T On the Cost of Persistence and Authentication in Skip Lists
%A Goodrich, Michael T.
%A Charalampos Papamanthou
%A Tamassia, Roberto
%E Demetrescu, Camil
%K Algorithm Analysis and Problem Complexity
%K algorithms
%K Computer Graphics
%K Data structures
%K Discrete Mathematics in Computer Science
%K Numeric Computing
%X We present an extensive experimental study of authenticated data structures for dictionaries and maps implemented with skip lists. We consider realizations of these data structures that allow us to study the performance overhead of authentication and persistence. We explore various design decisions and analyze the impact of garbage collection and virtual memory paging, as well. Our empirical study confirms the efficiency of authenticated skip lists and offers guidelines for incorporating them in various applications.
%B Experimental Algorithms
%S Lecture Notes in Computer Science
%I Springer Berlin Heidelberg
%P 94 - 107
%8 2007/01/01/
%@ 978-3-540-72844-3, 978-3-540-72845-0
%G eng
%U http://link.springer.com/chapter/10.1007/978-3-540-72845-0_8