We address the problem of implementing data structures resilient to memory faults, which may arbitrarily corrupt memory locations. In this framework, we focus on the implementation of dictionaries and perform a thorough experimental study using a testbed that we designed for this purpose. Our main discovery is that the best-known (asymptotically optimal) resilient data structures have very large space overheads. More precisely, most of the space used by these data structures is not due to key storage. This might not be acceptable in practice, since resilient data structures are meant for applications where a huge amount of data (often of the order of terabytes) has to be stored. Exploiting techniques developed in the context of resilient (static) sorting and searching, in combination with some new ideas, we designed and engineered an alternative implementation, which, while still guaranteeing optimal asymptotic time and space bounds, performs much better in terms of memory without compromising the time efficiency.

Data Structures Resilient to Memory Faults: An Experimental Study of Dictionaries / Ferraro Petrillo, U; Grandoni, Fabrizio; Italiano, Giuseppe Francesco. - In: ACM JOURNAL OF EXPERIMENTAL ALGORITHMICS. - ISSN 1084-6654. - 18:1(2013), pp. ---. [10.1145/2444016.2444022]

Data Structures Resilient to Memory Faults: An Experimental Study of Dictionaries

ITALIANO, GIUSEPPE FRANCESCO
2013

Abstract

We address the problem of implementing data structures resilient to memory faults, which may arbitrarily corrupt memory locations. In this framework, we focus on the implementation of dictionaries and perform a thorough experimental study using a testbed that we designed for this purpose. Our main discovery is that the best-known (asymptotically optimal) resilient data structures have very large space overheads. More precisely, most of the space used by these data structures is not due to key storage. This might not be acceptable in practice, since resilient data structures are meant for applications where a huge amount of data (often of the order of terabytes) has to be stored. Exploiting techniques developed in the context of resilient (static) sorting and searching, in combination with some new ideas, we designed and engineered an alternative implementation, which, while still guaranteeing optimal asymptotic time and space bounds, performs much better in terms of memory without compromising the time efficiency.
Data Structures Resilient to Memory Faults: An Experimental Study of Dictionaries / Ferraro Petrillo, U; Grandoni, Fabrizio; Italiano, Giuseppe Francesco. - In: ACM JOURNAL OF EXPERIMENTAL ALGORITHMICS. - ISSN 1084-6654. - 18:1(2013), pp. ---. [10.1145/2444016.2444022]
File in questo prodotto:
Non ci sono file associati a questo prodotto.
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11385/199787
Citazioni
  • Scopus 6
  • ???jsp.display-item.citation.isi??? ND
social impact