Rabin fingerprint

This item has been on the quality assurance side of the portal mathematics entered. This is done in order to bring the quality of the mathematics articles to an acceptable level .

Please help fix the shortcomings in this article and please join the discussion ! ( Enter article )

The Rabin fingerprint is a method for calculating a fingerprint . It was suggested by Michael O. Rabin .

method

An input polynomial and a key , both off , are required for the calculation . The fingerprint function is defined as. ${\ displaystyle A (x)}$ ${\ displaystyle P (x)}$ ${\ displaystyle \ mathbb {Z} _ {2} [x]}$ ${\ displaystyle f}$ ${\ displaystyle f (A) (x) = A (x) \ mod P (x)}$

use

The Rabin fingerprint is particularly suitable when used to recognize identical or similar sections in different files, i.e. H. to detect redundancy. This can then be used, for example, to optimize file transfer processes or to archive data. For example, the most used Massachusetts Institute of Technology developed the file system LBFS ( Low Bandwidth File System ) to Rabin fingerprint.

Individual evidence

↑ Michael O. Rabin : Fingerprinting by Random Polynomials . Center for Research in Computing Technology, Harvard University, 1981 ( PDF file; 465 kB [accessed December 9, 2014]).
↑ Purushottam Kulkarni, Fred Douglis, Jason D. LaVoie, John M. Tracey: Redundancy Elimination Within Large collections of files. In: USENIX Annual Technical Conference, General Track. May 12, 2004, pp. 59–72 , accessed on February 21, 2015 (English).

[rabin1981-1] Michael O. Rabin : Fingerprinting by Random Polynomials . Center for Research in Computing Technology, Harvard University, 1981 ( PDF file; 465 kB [accessed December 9, 2014]).

[kulkarni:usenix2004-2] Purushottam Kulkarni, Fred Douglis, Jason D. LaVoie, John M. Tracey: Redundancy Elimination Within Large collections of files. In: USENIX Annual Technical Conference, General Track. May 12, 2004, pp. 59–72 , accessed on February 21, 2015 (English).