Paper Info
Title
Biff (Bloom filter) codes: Fast error correction for large data sets
Abstract
Large data sets are increasingly common in cloud and virtualized environments. For example, transfers of multiple gigabytes are commonplace, as are replicated blocks of such sizes. There is a need for fast error-correction or data reconciliation in such settings even when the expected number of errors is small. Motivated by such cloud reconciliation problems, we consider error-correction schemes designed for large data, after explaining why previous approaches appear unsuitable. We introduce Biff codes, which are based on Bloom filters and are designed for large data. For Biff codes with a message of length L and E errors, the encoding time is O(L), decoding time is O(L + E) and the space overhead is O(E). Biff codes are low-density parity-check codes; they are similar to Tornado codes, but are designed for errors instead of erasures. Further, Biff codes are designed to be very simple, removing any explicit graph structures and based entirely on hash tables. We derive Biff codes by a simple reduction from a set reconciliation algorithm for a recently developed data structure, invertible Bloom lookup tables. While the underlying theory is extremely simple, what makes this code especially attractive is the ease with which it can be implemented and the speed of decoding. We present results from a prototype implementation that decodes messages of 1 million words with thousands of errors in well under a second.
Year
DOI
Venue
2012
10.1109/ISIT.2012.6284236
Information Theory Proceedings
Keywords
DocType
Volume
multiple gigabytes transfers,set reconciliation algorithm,fast error correction,large data sets,invertible bloom lookup tables,hash tables,error-correction schemes,encoding,space overhead,error correction codes,encoding time,virtualized environments,decoding speed,biff codes,data reconciliation,bloom filter,low-density parity-check codes,cloud reconciliation problems,parity check codes,decoding,decoding time,tornadoes
Conference
abs/1208.0798
ISSN
ISBN
Citations 
2157-8095 E-ISBN : 978-1-4673-2578-3
978-1-4673-2578-3
15
PageRank 
References 
Authors
0.74
12
2
Name
Order
Citations
PageRank
Michael Mitzenmacher17386730.89
George Varghese28149727.66