1
$\begingroup$

I was reading up on chunking and found Rabin fingerprinting is also used to break files into chunks. After reading about this algorithm, I understood how rolling hash is computed using Rabin fingerprint. This is explained almost everywhere. What I don't get is how in Rabin fingerprinting, we know to end one chunk here and start another? And how does insertion doesn't affect original chunks? Some sources mention the following, which I didn't get. (Although it's given with reference to LBFS, I think for de-duplication also chunking will be done in similar way.)

When the low 13 bits of the fingerprint are zero LBFS calls those 48 bytes a breakpoint and ends the current block and begins a new one. Since the output of Rabin fingerprints are pseudo-random the probability of any given 48 bytes being a breakpoint is 2^{-13}. This has the effect of shift-resistant variable size blocks.

We are checking if low 13 bits are 0 or not, because fingerprint is basically a remainder, after dividing by an irreducible polynomial? But even then, how does inserting something in chunk-1, still makes sure chunking will be shift-resistant?

Thanks in advance for the help!

Edit : I am talking about application of Rabin fingerprinting in breaking files into chunks for de-duplication. (Not for string search, I understood that one)

$\endgroup$
1
$\begingroup$

It depends on what you are using the Rabin rolling hash for. If you want to check whether a string P of length k is contained in a large string S, then the Rabin algorithm computes the Rabin hash of all substrings of S of length k. So, there are no decisions to make: every substring of length k gets hashed.

Other systems may use the Rabin hash for other purposes. There's more than one algorithm that uses this hash function. We can't tell you how "the algorithm" decides where to begin/end chunks without knowing what algorithm you are referring to.

$\endgroup$
  • $\begingroup$ I have edited the question. My only concern is chunking file for de-duplication. For string search, chunk length is already known to be size of pattern length. That's not an issue. $\endgroup$ – user270386 Oct 8 '17 at 5:08
  • $\begingroup$ @user270386, again, my answer is going to be the same: there are multiple ways that we could chunk a file for de-duplication; there's not a single answer. When you say "the algorithm", I think that's a misunderstanding -- there are multiple possible algorithms, with different tradeoffs. That's true even if we restrict attention to de-duplication. $\endgroup$ – D.W. Oct 8 '17 at 5:34
  • $\begingroup$ Okay, so if I understood this correctly, you mean, even Rabin fingerprinting can be used in multiple ways to create chunks? If so, can you please explain it only with reference to LBFS. (why if low 13 bits are 0, its called a breakpoint). Sorry for all the confusion. $\endgroup$ – user270386 Oct 8 '17 at 11:08
  • 1
    $\begingroup$ @user270386, I don't know what LBFS is. If you want to know something about LBFS, please edit the question to ask specifically about LBFS (rather than asking in general, as you currently do), and give a reference to where LBFS is defined. $\endgroup$ – D.W. Oct 8 '17 at 15:33
1
$\begingroup$

I know I'm very late to this question, but I want to try and provide an answer for anyone who stumbles across this as I have. I went and deciphered the original paper by Michael Rabin, and found that the Rabin-fingerprint was designed to NOT be shift-resistant. In his paper (http://www.xmailserver.org/rabin.pdf) he used the fingerprint to detect any data-modification in files as the fingerprint would be different if any bit was changed. So, I have no idea why the LBFS paper is claiming to use fingerprinting for dynamic chunk borders because that's exactly what it is not meant for. Look for a different rolling hash if you want shift-resistant chunk borders. That being said fingerprinting would be a great way to check whether two chunks are the same or not.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.