rabin fingerprint and sketch

2 files changed, 23 insertions, 0 deletions

diff --git a/pdf/doc.bib b/pdf/doc.bib
index 73107c0..b28cbda 100644
--- a/pdf/doc.bib
+++ b/pdf/doc.bib
@@ -60,6 +60,14 @@
   publisher={Nature Publishing Group}
 }
 
+@article{rabin1981fingerprinting,
+  title={Fingerprinting by random polynomials},
+  author={Rabin, Michael O},
+  journal={Technical report},
+  year={1981},
+  publisher={Center for Research in Computing Technology, Harvard University}
+}
+
 @inproceedings{zhang2006hptfs,
   title={Hptfs: A high performance tape file system},
   author={Zhang, Xianbo and Du, David and Hughes, Jim and Kavuri, Ravi and StorageTek, Sun},
diff --git a/pdf/doc.tex b/pdf/doc.tex
index 996742d..1de09ad 100644
--- a/pdf/doc.tex
+++ b/pdf/doc.tex
@@ -410,9 +410,24 @@ En effet, lorsqu'une nouvelle version est traitée par le pipeline,
 il faut appliquer la fonction de hachage sur tous les chunks possibles, octet par octet, des données de cette version.
 Une fonction optimisée pour ce type de traitement apportera donc un gain de performances non négligeable.
 
+Nous avons choisi pour cet usage l'empreinte de Rabin~\cite{rabin1981fingerprinting}, car c'est une fonction de hachage sur fenêtre glissante efficiente et populaire et parce qu'elle sera également utilisée pour calculer le \emph{sketch} des chunks.
 
 \subsection{Sketch}
 
+Le \emph{sketch} est ce qu'on appelle un \emph{hash de ressemblance}.
+Il correspond en fait à une fonction de hachage dont la répartition n'est pas du tout uniforme,
+mais au contraire, fait correspondre la même signature à des données différentes si elles sont similaires.
+
+De manière intuitive, les sketches de similitude fonctionnent en identifiant des portions d'un chunk
+qui ne changeraient probablement pas si de faibles variations sont introduites ;
+on appelle ces portions des ``features''.
+Une des manières de procéder est d'utiliser une fonction de hachage sur une fenêtre glissante de petite taille
+(e.g. 32~octets) et de choisir la valeur maximale obtenue en tant que feature.
+En utilisant différentes fonctions de hash on peut ainsi obtenir plusieurs features.
+
+La méthode exacte utilisée est celle décrite par Philip Shilane \etal~\cite{shilane2012wan}.
+Elle s'appuie sur l'empreinte de Rabin~\cite{rabin1981fingerprinting} que l'on décline en différentes fonctions de hachage pour obtenir plusieurs features.
+
 
 \subsection{Index des signatures}
 % TODO: parler des sketches, fingerprints et de l'index entier