Petrillo, Umberto Ferraro and Grandoni, Fabrizio and Italiano, Giuseppe F. (2013) Data structures resilient to memory faults: An experimental study of dictionaries. Journal of Experimental Algorithmics, 18. ISSN 1084-6654
Full text not available from this repository.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.
| Item Type: | Scientific journal article, Newspaper article or Magazine article |
|---|---|
| Subjects: | Computer sciences |
| Department/unit: | Dipartimento tecnologie innovative > Istituto Dalle Molle di studi sull’intelligenza artificiale USI-SUPSI |
| Depositing User: | Fabrizio Grandoni |
| Date Deposited: | 14 Mar 2014 08:20 |
| Last Modified: | 23 May 2016 14:18 |
| URI: | http://repository.supsi.ch/id/eprint/4473 |
Actions (login required)
 |
View Item |