Riad Mokadem [email protected] Signatures Algébriques dans les Systèmes de Gestion de Données Scalables et Distribuées SDDS-2005 Encadré par : Pr

Riad Mokadem

[email protected]

Signatures Algébriques dans Signatures Algébriques dans les Systèmes de Gestion de les Systèmes de Gestion de

Données Scalables et Données Scalables et Distribuées SDDS-2005Distribuées SDDS-2005

Encadré par : Pr W.Litwin Séminaire de Recherche CERIA

15 Décembre 2005

Les SDDSsLes SDDSsProblématiqueProblématiqueSignatures AlgébriquesSignatures Algébriques Signatures Algébriques Pré Signatures Algébriques Pré Calculées cumulativesCalculées cumulativesEncodage / Décodage de donnéesEncodage / Décodage de donnéesAlgorithmes de Karp-Rabin, Boyer Algorithmes de Karp-Rabin, Boyer Moore.Moore.Recherche de caractèresRecherche de caractères

Recherche complète, par préfixe, par chaîne, Recherche complète, par préfixe, par chaîne, plus grand préfixe commun, plus grande chaîne plus grand préfixe commun, plus grande chaîne

commune.commune.

Protection contre la corruption dans SDDS-2005Protection contre la corruption dans SDDS-2005 Mesures de Performances Mesures de Performances ComparaisonsComparaisonsPerspectives et ConclusionPerspectives et Conclusion

PlanPlan

3

Multi-ordinateurMulti-ordinateur

Architecture Matérielle: Multi-ordinateur

Ressource Disque local

Ram distant

(Ethernet)

Ram distant

(Giga bit)

Ram locale

Temps d’accès 10msec 100 µsec 1 µsec 100nsec

4

Architecture SDDS-2005Architecture SDDS-2005

Réseau

Serveur

Cases en RAM

Client

SDDS-CP

Applications

Client

Applications

Client

Applications

Client

Applications

SDDS-CPSDDS-CP SDDS-CP

SDDS-CP

...

Serveur

Cases en RAM

SDDS-CP

...

Serveur

Cases en RAM

SDDS-CP

...

Serveurde

Noms

SDDS-CP

Serveurd'index RP*S

SDDS-CP

...

...

Architecture SDDS 2005Architecture SDDS 2005

5

Problématique ?Problématique ?

- Données visibles par les utilisateurs.

- Différents types de recherche coûtants

Utilisation des signatures cumulatives pour la recherche et contre les vues accidentelles des données

Encodage\ Décodage des données par le client (Données codées sur les serveurs).

différentes possibilités de recherches

6

Structure de DonnéesStructure de Données

Key DataKey Data Non Key DataNon Key Data

Structure d’un enregistrementStructure d’un enregistrement

Le codage décodage concerne les données non cléLe codage décodage concerne les données non clé

Le codage décodage est transparent pour le serveur et les signatures Le codage décodage est transparent pour le serveur et les signatures sont calculées au niveau du client.sont calculées au niveau du client.

Limite des 256B pour les donnéesLimite des 256B pour les données

7

Signatures AlgébriquesSignatures AlgébriquesStructure de corps de Galois fini GF(Structure de corps de Galois fini GF(2f ) ) f f>>1>>1

Chaque symbole du corps de longueur Chaque symbole du corps de longueur ff

Utilisation de Xor pour les opérations + et – .Utilisation de Xor pour les opérations + et – .

Utilsation de tables Antilog et Log pour X et / .Utilsation de tables Antilog et Log pour X et / .

Existence d’un élément primitif Existence d’un élément primitif

Signature algébrique Sign ( P )= pi i i = 1..n

Tels que P=(p1,p2,…,pn) ( = : = : , 2, 3… )Signature sur N symboles:Signature sur N symboles:

Sign (P)= (Sign ( P ), Sign 2( P ),…Sign N ( P ))

8

Signatures Algébriques dans Signatures Algébriques dans SDDS-2005SDDS-2005

Utilisation des signatures algébriques dans SDDS-2004:Utilisation des signatures algébriques dans SDDS-2004:

* Stockage sur le disque.* Stockage sur le disque.

- Calcul de signatures pour les pages de données - Calcul de signatures pour les pages de données et stockage des pages mises à jour.et stockage des pages mises à jour.

* Gestion de concurrence (Mise à jour).* Gestion de concurrence (Mise à jour).

- Comparaison entre la signature avant et la - Comparaison entre la signature avant et la signature après d’un enregistrement lors d’une signature après d’un enregistrement lors d’une mise à jour.mise à jour.

* Recherche complète de chaîne dans les enregistrements.* Recherche complète de chaîne dans les enregistrements.

9

Signatures Algébriques:Recherche de Signatures Algébriques:Recherche de Chaînes Chaînes (SDDS-2004):(SDDS-2004): Recherche Complète de Recherche Complète de DonnéeDonnée

Recherche d’une chaîne de signature S

* Le client envoi la signature S de la chaîne à rechercher

* Parcours séquentiel des enregistrements

* Comparaison avec les signatures algébriques stockées au niveau de chaque en-tête d’enregistrement.(Test sur le 1er symbole puis le 2 ème en cas d’égalité)

Lr : Longer of record.

Es: Pointer to next record

K: Key of record.

Lc: Version

Sg: Signature of record.

Lr Es K Lc Sg Data

Record Structure

Comparaison avec la signature stockée au niveau de chaque enregistrement

10

Signatures AlgébriquesSignatures AlgébriquesCumulativesCumulatives

Encodage de pi :

p’i=pi i = antilog (log pi+i)

p’’i= p’’i-1 + p’i = p’’i-1 XOR p’i

Décodage de Pi :

pi=p’i / i = antilog (log p’i- i)

p’i= p’’i - p’’i-1= p’’i XOR p’’i-1

11

Signatures Algébriques Signatures Algébriques CumulativesCumulatives

Exemple:

P=« CERIA_SEMINAIRE» Encodage

P’’=(p’’1,p’’2,….p’’15)=( C, p’’1+ 2E,….,p’’14+ 15E)

Sign2(P)= C+ 2E+….+ 15E

Décodage

p’i= p’’i - p’’i-1 p’2= p’’2 - p’’1

pi = p’i / i p2= p’2 / i

12

Cas SDDS-2005

Signatures algébriques pour la recherche complèteN=2 (N nombre de symboles constituant la signature)

F=16

Signatures cumulatives pour la recherche de chaines

N=2F= 16

Probabilité de collision de 2-Nf.

GF(28) chaînes Code ASCII

GF(216 ) chaînes dans Unicode

13

Recherche de DonnéesRecherche de Données

Pas d’Envoi de données lors de certaines Pas d’Envoi de données lors de certaines recherches recherches Envoi de signatures. Envoi de signatures.

Données encodées. Signatures pré-calculées.Plusieurs algorithmes disponibles: Boyer Plusieurs algorithmes disponibles: Boyer

Moore, Karp Rabin…Moore, Karp Rabin…

14

Encodage / DécodageEncodage / DécodageRequête de RechercheRequête de Recherche

Client

Serv1

Serv2

Serv3

Requête de Requête de RechercheRecherche

Comparaison des signatures

Envoi du résultat Envoi du résultat de la recherchede la recherche

DécodageDécodage

Encodage Encodage à à

l’insertionl’insertion

15

Recherche de Chaînes dans SDDS-2005Recherche de Chaînes dans SDDS-2005Recherche du PréfixeRecherche du Préfixe

Recherche de Préfixe

- Le client envoi la signature Sc et la taille du préfixe m.

Au serveur:

- Lecture dans l’enregistrement de la signature Sm.

- Comparaison entre Sc et Sm. Sauvegarde l’enregistrement en cas d’égalité.

- Passage à l’enregistrement suivant.

- Vérification de Collision et envoi des enregistrements sélectionnés au client.

Complexité de la Recherche: O(1)

16

Recherche de Chaînes dans SDDS-2005Recherche de Chaînes dans SDDS-2005Recherche du PréfixeRecherche du Préfixe

Signature cumulative de UNIVERSITE PARIS

= Sign (S)

UNIVERSITE PARIS DAUPHINE

Signature cumulative de UNIVERSITE PARIS DAUPHINE

= Sign (E)

- Sc Sign (U)

- ….Sc= Sign (S) Préfixe trouvé

17

Recherche de Chaînes dans SDDS-2005Recherche de Chaînes dans SDDS-2005Recherche PartielleRecherche Partielle

Recherche de chaîne partielle* Le client envoi la signature Sc et la taille de donnée l.

•Au niveau du serveur:

i=1;

1- Lecture de la signature Ss sur le préfixe de longueur L.

Si Ss=Sc, l’enreg est sélectionné dans la liste des enregistrements envoyés au client.

2- Si i+l = n (taille de l’enregistrement) et Ss Sc passer à l’enreg suivant.

18


2.1 Ss := Ss XOR p’i XOR p’l + i

2.2 Sc := antilog (log Sc + 1).

3. Si Ss=Sc Chaine trouvé et l’enreg est sélectionné

Sinon ( Ss Sc) pas de chaîne trouvée

i := i + 1;

Revenir à (2) jusqu’au dernier caractère p’ de l’enreg.

4. passer à l’enregistrement suivant

19


Exemple:

- Recherche de la chaîne « PARIS »

- Le client envoi la signature cumulative Sc des 5 caractères à rechercher

et la taille L=5. UNIVERSITE PARIS DAUPHINE

….Au niveau du serveur:

- Parcourt séquentiel suivant des chaînes de 5 caractères et compraison de signatures.

Sign(E)!=Sc, Sign(R)!=Sc,….Sign(S)=Sc Chaîne trouvée

- Vérification de Collision sur les enregistrements trouvés.

Complexité de la Recherche: O(n)

20

Recherche de Chaînes dans SDDS-2005Recherche de Chaînes dans SDDS-2005Recherche du Plus Grand PréfixeRecherche du Plus Grand Préfixe

Le client envoi le préfixe encodée de données. S’’=s’’Le client envoi le préfixe encodée de données. S’’=s’’11s’’s’’22…s’’…s’’ll à l’ensemble des serveursà l’ensemble des serveurs

-1. Trouver le 1-1. Trouver le 1erer enreg tels que p’’ enreg tels que p’’11=s’’=s’’11..

u=1;//Test si p’’u=1;//Test si p’’22= s’’= s’’22..

-2. Parcourir l’enreg suivant 22. Parcourir l’enreg suivant 2uu.i=2.i=2u u

-3. tant que p’’3. tant que p’’ii=s’’=s’’ii et 2 et 2uu<n <n u:=u+1; L=u;u:=u+1; L=u;

Soit j=(2Soit j=(2u u + 2+ 2u-1u-1)/2)/2

Si p’’Si p’’jj=s’’=s’’jj Recherche dans [j,p’’ Recherche dans [j,p’’uu] L:=j] L:=j

Sinon recherche dans [p’’Sinon recherche dans [p’’u-1u-1,j],j]

Revenir à (3)Revenir à (3)

21


- Rajouter l’enregistrement à la liste. Soit s’’- Rajouter l’enregistrement à la liste. Soit s’’LL sa sign cumulative sa sign cumulative

- Examiner le prochains enregistrement:- Examiner le prochains enregistrement:

- Test Si p’’- Test Si p’’11=s’’=s’’LL u=L revenir à (1). (en multipliant par u=L revenir à (1). (en multipliant par L )

- Déterminer nouveau L- Déterminer nouveau L

Chaque serveur répond au client en envoyant un message comportant la Chaque serveur répond au client en envoyant un message comportant la taille du plus grand préfixe et les différents enregistrements concernés.taille du plus grand préfixe et les différents enregistrements concernés.

Complexité de la Recherche par enregistrement: Entre O(1) et O(Log 2m).

(M taille du préfixe commun)

22


UNIVERSITEDAUPHINEEnreg1 P

UNIVERSITEPARIS9 DAUPHINEEnreg2 P’

UNIVERSITEPARIS_ DAUPHINEChaîne S

Enregistrement1: Comparaion entre P et S. Enregistrement1: Comparaion entre P et S. Egalité sur p1, p2, p4, p8.Egalité sur p1, p2, p4, p8.

Inégalité sur p16, p12.Inégalité sur p16, p12.

Egalité ur p10.Egalité ur p10.

Inégalité sur p11 Inégalité sur p11 L=10 L=10

Enregistrement2: Comparaion entre P’ et S.Enregistrement2: Comparaion entre P’ et S. Egalité sur p1, p2, p4, p8.Egalité sur p1, p2, p4, p8.

Inégalité sur p16.Inégalité sur p16.

Egalité ur p12, p14, p15. Egalité ur p12, p14, p15. L=15 L=15

23

Recherche de Chaînes dans SDDS-2005Recherche de Chaînes dans SDDS-2005Plus Grande Chaîne CommunePlus Grande Chaîne Commune

Le client envoi la chaîne encodée de données. S’’=s’’Le client envoi la chaîne encodée de données. S’’=s’’11s’’s’’22…s’’…s’’m m à l’ensemble à l’ensemble des serveurs.des serveurs.

( Appliquer l’algorithme du plus grand préfixe sur chaque caractère )( Appliquer l’algorithme du plus grand préfixe sur chaque caractère )

i:=1;j:=1;i:=1;j:=1;

-1. -1. Si p’’ Si p’’jj=s’’=s’’ii k:=i;k:=i;

appliquer l’Algorithme du plus grand préfixeappliquer l’Algorithme du plus grand préfixe

Déterminer Déterminer LL

i:=k+1; j:=1; revenir à (1)i:=k+1; j:=1; revenir à (1)

sinon j:=j+1, si j < n-L revenir à (1);sinon j:=j+1, si j < n-L revenir à (1);

-2. i:=i+1; si i < m et m-i<L j=1;revenir à (1)-2. i:=i+1; si i < m et m-i<L j=1;revenir à (1)

sinon Enregistrement suivantsinon Enregistrement suivant

n Taille de l’enreg.

m Taille de la chaîne

L Taille de la plus grande chaîne commune

24

Recherche de Chaînes dans SDDS-2005Recherche de Chaînes dans SDDS-2005Plus Grande Chaîne CommunePlus Grande Chaîne Commune

UNIVERSITEDAUPHINEEnreg1 P

UNIVERSITEPARISDAUPHINE9Enreg2 P’

SEMINAIREPARISDAUPHINEChaîne S

Enregistrement1: L= 8Enregistrement1: L= 8

Enregistrement2: L= 13Enregistrement2: L= 13

Complexité de la Recherche par enregistrement: Entre O(n-L) (m-L)et O(nm).

(n Taille de l’enreg, m taille de la chaîne envoyée par le client, L la taille de chaîne commune la plus longue)

….

25

Protection contre la collision lors de la Protection contre la collision lors de la Recherche dans SDDS-2005Recherche dans SDDS-2005

A la fin de la recherche, résolution collision donnés.A la fin de la recherche, résolution collision donnés.

Deux possibilités:Deux possibilités:

* Résolution au niveau du client.* Résolution au niveau du client.

- Risque de recherche à nouveau sur l’ensemble des serveurs - Risque de recherche à nouveau sur l’ensemble des serveurs en cas de collision.en cas de collision.

* Résolution au niveau des serveurs (Notre choix).* Résolution au niveau des serveurs (Notre choix).

- comparaisons en parallèle.- comparaisons en parallèle.

Comparaison caractère par caractère entre la chaîne reçue et le contenu de Comparaison caractère par caractère entre la chaîne reçue et le contenu de l’enregistrement sélectionné.l’enregistrement sélectionné.

Relancer la recherche en cas de collision (caractére par caractére)Relancer la recherche en cas de collision (caractére par caractére)

26

Recherche de CRecherche de Chaînes:haînes:AlgorithmeAlgorithme de Karp-Rabin de Karp-Rabin

Une sous chaîne peut être considérée comme un nombre entier en base d (f=8 est la taille de l'alphabet,

M taille de la chaîne à rechercher)

P’i = pifM-1+pi+1fM-2+ … +pi+M-2f+pi+M-1

La valeur pour la sous chaîne commençant à la position suivante peut être calculée à l'aide de l'expression:

p’i+1 = (p’i-pifM-1)*f+pi+M

27

Mesures de Performances Mesures de Performances (Codage / Décodage de Données)(Codage / Décodage de Données)

Encodage : 0.045ms/KBEncodage : 0.045ms/KB

Décodage : 0.042ms/KBDécodage : 0.042ms/KB

Insertion : 0.25ms/KBInsertion : 0.25ms/KB

Faible coûtFaible coût

Recherche de données plus rapide Protection contre la vue accidentelle de ces données

28

Mesures de Performances Mesures de Performances (Signatures Cumulative)(Signatures Cumulative)

Record Record String Offset Time

Position Size Size (msec)

1 20 5 13 0.44

1 100 20 70 0.68

1 100 20 80 0.682

100 100 20 70 72.5 100 100 30 70 71.7 200 100 20 70 165

Record Record Préfix Time

Position Size Size (msec)

1 250 20 0.369

100 250 20 37.8

100 250 35 37.78

200 250 20 71.3

300 250 20 120.53

500 250 20 197.5

Temps de recherche de chaînes

Temps de recherche de Préfixes

L’utilisation de Modulo pour remédier à la limite de taille de données (255) augmente le temps de recherche de 1% à 2%.

29

Mesures de PerformancesMesures de Performances

(Signatures Cumulative)(Signatures Cumulative)Position enreg Taille donnes

inséréesTaille dernier

enregTaille prefixe à

rechercherTemps de

recherche (ms)

1 50 50 25 0.456

1/100 250 50 25 43

49/100 250 50 25 46.2

99/100 250 50 25 47

Position enreg Taille donnesinsérées

Taille dernier enreg

(préfixe)

Taille de la chaîne à rechercher

Offset chaîne dans

enregistrement

Temps de recherche

(ms)

1 100 100 22 70 0.62

100 100 22 10 10 290

100 100 45 15 10 470

100 120 45 15 10 565

Temps de recherche du plus grand Préfixe

Temps de recherche de la plus grande chaîne commune

Existence de plus grands préfixes intermédiaires

}

30

ComparaisonsComparaisons

Size of case

Size of records

Size of last record

Size data to search

Offset in last Record

Algebraic Signature Search

Karp Rabin Search

Cumu-latives sign Search

100 250 25 10 5 205 151 147

200 250 25 10 5 368 275 268

500 250 25 10 5 1123 725 702

1000 250 25 10 5 2254 1580 1526

Tableau comparatif pour la recherche de chaîne dans un enregistrement

31

ComparaisonsComparaisons

Temps de recherche de chaînes réduits:Temps de recherche de chaînes réduits:

--Algorithmes existants (karp-Rabin)Algorithmes existants (karp-Rabin)

Gain de 5% pour les données<32BGain de 5% pour les données<32B

Gain de + de 20% pour les données>32BGain de + de 20% pour les données>32B

-Données non encodées (Gain de 30%). -Données non encodées (Gain de 30%).

Comparaison entre Temps de Recherches

0

500

1000

1500

2000

2500

100 200 500 1000

Taille de la case de données

Tem

ps

de

Rec

her

che

SignAlgébriques

Karp Rabin

SignCumulatives

(Ms)

(MB)

32

Recherche dans SDDS-2005Recherche dans SDDS-2005

}}

}}Recherche par cléRecherche par clé

Recherche par le contenuRecherche par le contenu

Interface du Client pour différents types de recherche s dans SDDS-2005

33

Exemple de Recherche de Préfixe dans SDDS-2005Exemple de Recherche de Préfixe dans SDDS-2005

Résultat provenant du serveur au niveau Résultat provenant du serveur au niveau du Client SDDS-2005du Client SDDS-2005

Lancement de la recherche du Préfixe au Lancement de la recherche du Préfixe au niveau de l’applicationniveau de l’application

34

PerspectivesPerspectives

Autres méthodesAutres méthodes: : (à implémenter)(à implémenter)--Utilisation du schéma de Horner( signatures inverséesUtilisation du schéma de Horner( signatures inversées ))

SigSignn=p=p11ααnn+p+p22ααn-1+….+ppnnαα1 1 =(p=(p1αα+p+p22))αα+p+p33) ) αα ….+ppnnαα

-Utilisation de table de Broder, de multiplication de -Utilisation de table de Broder, de multiplication de polynômes, de table multiplication par polynômes, de table multiplication par αα

Plus rapide

35

Perspectives: Protection contre la Perspectives: Protection contre la corruption dans SDDS-2005corruption dans SDDS-2005

Au moment de l’insertion de donnéesAu moment de l’insertion de données

Pour chaque 255 caractèresPour chaque 255 caractères

Calcul du 2Calcul du 2èmeème

symbole de la signature s2(élément primitif symbole de la signature s2(élément primitif αα22 ) )

Sauvegarde au niveau du client de s2.Sauvegarde au niveau du client de s2.

Au moment du décodageAu moment du décodage ::

Calcul de la signature s’2 sur l’enregistrement provenant du serveurCalcul de la signature s’2 sur l’enregistrement provenant du serveur

Comparaison avec la signature stockée Comparaison avec la signature stockée

Détection de corruption en cas d’inégalitéDétection de corruption en cas d’inégalité

Probabilité de non détection de corruption de données 1/2Probabilité de non détection de corruption de données 1/2nfnf

36

Perspectives: Perspectives: Compression delta pour les mise à Compression delta pour les mise à jour distribuées de données dans GF(2jour distribuées de données dans GF(21616):):

A chaque insertionA chaque insertion: :

Calcul de la sign cumulative (2 symboles) chaque 256 car et stockage de Calcul de la sign cumulative (2 symboles) chaque 256 car et stockage de s2 dans la structure de l’enregs2 dans la structure de l’enreg..

A chaque mise à jour (normale))::Recherche->Comparaison entre l’image avant et arrière au niveau du Recherche->Comparaison entre l’image avant et arrière au niveau du dernier car de la signature:dernier car de la signature:

*Egalité*Egalité Pas de mise à jour Pas de mise à jour

*Différence: comparaison au milieu de l’enreg....*Différence: comparaison au milieu de l’enreg....

Déterminer la partie mise à jour Déterminer la partie mise à jour

Même principe pour le Même principe pour le stockagestockage (Déterminer les pages (Déterminer les pages modifiées)modifiées)

37

Exemple de stockage dans SDDS-2005Exemple de stockage dans SDDS-2005

Listing d’exécution sur Server SDDS-2005 Listing d’exécution sur Server SDDS-2005(Cas de signatures algébriques)(Cas de signatures algébriques)

1ére Requête de stockage : 1ére Requête de stockage : New File New File calcul de Signature s (375 ms) calcul de Signature s (375 ms) sauvegarde sur disque de toutes sauvegarde sur disque de toutes les pages (4922 ms)les pages (4922 ms)

2ème Requête de stockage : 2ème Requête de stockage : Pas de changement (375 ms) Pas de changement (375 ms)

3ème Requête de 3ème Requête de stockage : stockage : 1 page mise à jour 1 page mise à jour

(375 + 16 ms)(375 + 16 ms)

Amélioration de ces temps en utilisant les signatures Pré Calculées Cumulatives

38

ConclusionConclusion

- Implémentation de nouvelles primitives - Implémentation de nouvelles primitives de recherche, mise à jour et stockage.de recherche, mise à jour et stockage.

( Prototype SDDS-2005 )( Prototype SDDS-2005 )

En téléchargement sur En téléchargement sur http:\ceria.dauphine.fr

39

RéférencesRéférences- - W Litwin, R.Mokadem & Th.Schwarz Pre-computed Algebraic Signatures for W Litwin, R.Mokadem & Th.Schwarz Pre-computed Algebraic Signatures for faster string search. Protection against incidental viewing and corruption of Data faster string search. Protection against incidental viewing and corruption of Data in an SDDS. Proceeding of third international workshop and co-located with the in an SDDS. Proceeding of third international workshop and co-located with the 3131stst international conference on very large data bases (DBISP2P 2005). international conference on very large data bases (DBISP2P 2005). Trondheim, Norway. August 2005.Trondheim, Norway. August 2005.

- W Litwin, R Mokadem, Thomas Schwarz.: "- W Litwin, R Mokadem, Thomas Schwarz.: "Disk Backup Through Algebraic Disk Backup Through Algebraic Signatures in Scalable and Distributed Data StructuresSignatures in Scalable and Distributed Data Structures", Proceedings of the Fifth ", Proceedings of the Fifth Workshop on Distributed Data and Structures, Thessaloniki, June 2003 (WDAS Workshop on Distributed Data and Structures, Thessaloniki, June 2003 (WDAS 2003). 2003). http://ceria.dauphine.fr/Riad/Article_storage-wdas_wl.pdfhttp://ceria.dauphine.fr/Riad/Article_storage-wdas_wl.pdf

--M. Crochemore andM. Crochemore and T.Lecroq, Pattern Matching and Text Compression T.Lecroq, Pattern Matching and Text Compression AlgorithmAlgorithm, in , in The Computer Science and Engineering HandbookThe Computer Science and Engineering Handbook, A.B. Tucker, , A.B. Tucker, Jr, ed., CRC Press, Boca Raton, 2003, Chapter 8. To appear. Jr, ed., CRC Press, Boca Raton, 2003, Chapter 8. To appear.

Litwin, W., Schwarz, Th. Algebraic Signatures for Scalable Distributed Data Litwin, W., Schwarz, Th. Algebraic Signatures for Scalable Distributed Data Structures. IEE Intl. Conf. On Data Eng., ICDE-04, 2004.Structures. IEE Intl. Conf. On Data Eng., ICDE-04, 2004.

Karp, R. M., Rabin, M. O.Karp, R. M., Rabin, M. O. Efficient randomized pattern-matching algorithms. Efficient randomized pattern-matching algorithms. IBM Journal of Research and Development, Vol. 31, No. 2, March 1987.IBM Journal of Research and Development, Vol. 31, No. 2, March 1987.

Ingold Rolf.2004 Ingold Rolf.2004 Programmation 3A: Algorithmique. Recherche de sous-chaînes. Université of Fribourg.2004

FINFIN

Merci Merci

[email protected]@Dauphine.frne.fr

Documents

Riad Mokadem [email protected] Signatures Algébriques dans les Systèmes de Gestion de Données Scalables et Distribuées SDDS-2005 Encadré par : Pr