{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:23:26Z","timestamp":1750307006759,"version":"3.41.0"},"reference-count":26,"publisher":"Association for Computing Machinery (ACM)","license":[{"start":{"date-parts":[[2013,4,19]],"date-time":"2013-04-19T00:00:00Z","timestamp":1366329600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["ACM J. Exp. Algorithmics"],"published-print":{"date-parts":[[2013,12]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1145\/2444016.2444022","type":"journal-article","created":{"date-parts":[[2013,5,7]],"date-time":"2013-05-07T20:51:42Z","timestamp":1367959902000},"source":"Crossref","is-referenced-by-count":3,"title":["Data structures resilient to memory faults"],"prefix":"10.1145","volume":"18","author":[{"given":"Umberto","family":"Ferraro-Petrillo","sequence":"first","affiliation":[{"name":"Universit\u00e0 di Roma \u201cLa Sapienza\u201d, Rome, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Fabrizio","family":"Grandoni","sequence":"additional","affiliation":[{"name":"Dalle Molle Institute, Manno, Switzerland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giuseppe F.","family":"Italiano","sequence":"additional","affiliation":[{"name":"Universit\u00e0 di Roma \u201cTor Vergata\u201d, Roma, Italy"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2013,4,19]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/103418.103469"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/0404042"},{"volume-title":"Proceedings of the 37th Annual Symposium on Foundations of Computer Science (FOCS'96)","author":"Aumann Y.","key":"e_1_2_1_3_1","unstructured":"Aumann , Y. and Bender , M. A . 1996. Fault tolerant data structures . In Proceedings of the 37th Annual Symposium on Foundations of Computer Science (FOCS'96) . IEEE Computer Society, Los Alamitos, CA, USA, 580--. Aumann, Y. and Bender, M. A. 1996. Fault tolerant data structures. In Proceedings of the 37th Annual Symposium on Foundations of Computer Science (FOCS'96). IEEE Computer Society, Los Alamitos, CA, USA, 580--."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167129"},{"key":"e_1_2_1_5_1","unstructured":"Boyer R. S. and Moore J. S. 1982. MJRTY\u2014a fast majority vote algorithm. http:\/\/www.cs.utexas.edu\/ftp\/techreports\/tr81-32.pdf.  Boyer R. S. and Moore J. S. 1982. MJRTY\u2014a fast majority vote algorithm. http:\/\/www.cs.utexas.edu\/ftp\/techreports\/tr81-32.pdf."},{"volume-title":"Proceedings of the 15th Annual European Symposium on Algorithms (ESA'07)","author":"Brodal G. S.","key":"e_1_2_1_6_1","unstructured":"Brodal , G. S. , Fagerberg , R. , Finocchi , I. , Grandoni , F. , Italiano , G. F. , J\u00f8rgensen , A. G. , Moruz , G. , and M\u00f8lhave , T . 2007. Optimal resilient dynamic dictionaries . In Proceedings of the 15th Annual European Symposium on Algorithms (ESA'07) . Springer-Verlag, Berlin, 347--358. Brodal, G. S., Fagerberg, R., Finocchi, I., Grandoni, F., Italiano, G. F., J\u00f8rgensen, A. G., Moruz, G., and M\u00f8lhave, T. 2007. Optimal resilient dynamic dictionaries. In Proceedings of the 15th Annual European Symposium on Algorithms (ESA'07). Springer-Verlag, Berlin, 347--358."},{"volume-title":"Proceedings of the 23rd International Colloquium on Automata, Languages and Programming (ICALP'96)","author":"Chlebus B. S.","key":"e_1_2_1_7_1","unstructured":"Chlebus , B. S. , Gambin , A. , and Indyk , P . 1996. Shared-memory simulations on a faulty-memory DMM . In Proceedings of the 23rd International Colloquium on Automata, Languages and Programming (ICALP'96) . Springer-Verlag, Berlin, 586--597. Chlebus, B. S., Gambin, A., and Indyk, P. 1996. Shared-memory simulations on a faulty-memory DMM. In Proceedings of the 23rd International Colloquium on Automata, Languages and Programming (ICALP'96). Springer-Verlag, Berlin, 586--597."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539791195877"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/11841036_68"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/3118767.3119110"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13193-6_1"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13193-6_34"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/11561071_1"},{"volume-title":"Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'07)","author":"Finocchi I.","key":"e_1_2_1_14_1","unstructured":"Finocchi , I. , Grandoni , F. , and Italiano , G. F . 2007. Resilient search trees . In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'07) . SIAM, Philadelphia, 547--553. Finocchi, I., Grandoni, F., and Italiano, G. F. 2007. Resilient search trees. In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'07). SIAM, Philadelphia, 547--553."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2009.07.026"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9088-4"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022802010738"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP'04)","author":"Henzinger M.","year":"2004","unstructured":"Henzinger , M. 2004 . The past, present and future of web search engines (invited talk) . In Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP'04) . Springer. Henzinger, M. 2004. The past, present and future of web search engines (invited talk). In Proceedings of the 31st International Colloquium on Automata, Languages and Programming (ICALP'04). Springer."},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'07)","author":"Henzinger M.","year":"2007","unstructured":"Henzinger , M. 2007 . Combinatorial algorithms for web search engines: Three success stories . In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'07) . SIAM, Philadelphia, 1022--1026. Henzinger, M. 2007. Combinatorial algorithms for web search engines: Three success stories. In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'07). SIAM, Philadelphia, 1022--1026."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796305298"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/T-ED.1979.19370"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00303-6"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804351"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1555349.1555372"},{"key":"e_1_2_1_25_1","unstructured":"Tezzaron Semiconductor. 2004. Soft Errors in electronic memory\u2014A white paper. Tech. rep. http:\/\/www. tezzaron.com\/about\/papers\/soft_errors_1_1_secure.pdf.  Tezzaron Semiconductor. 2004. Soft Errors in electronic memory\u2014A white paper. Tech. rep. http:\/\/www. tezzaron.com\/about\/papers\/soft_errors_1_1_secure.pdf."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/0214009"}],"container-title":["ACM Journal of Experimental Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2444016.2444022","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2444016.2444022","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:48:57Z","timestamp":1750236537000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2444016.2444022"}},"subtitle":["An experimental study of dictionaries"],"short-title":[],"issued":{"date-parts":[[2013,4,19]]},"references-count":26,"alternative-id":["10.1145\/2444016.2444022"],"URL":"https:\/\/doi.org\/10.1145\/2444016.2444022","relation":{},"ISSN":["1084-6654","1084-6654"],"issn-type":[{"type":"print","value":"1084-6654"},{"type":"electronic","value":"1084-6654"}],"subject":[],"published":{"date-parts":[[2013,4,19]]}}}