W d'ordre
THESE
présentée
à
L'UNIVERSITE PARIS-IX DAUPHINE
U.F.R Sciences des Organisations
pour obtenir le titre de
DOCTEUR
EN
SCIENCE
Spécialité:
INFORMATIQUE
par
Samba
NDIAYE
Sujet:
UTILiSATION DES COURBES DE PEANO-HILBERT
POUR LA GESTION DES OBJETS
DANS LES BASES DE DONNEES SPATIALES
Soutenue le 14 septembre 1993 devant le jury composé de:
MM
C.BERTHET
Président
G.BOULAYE
Rapporteur
E.FEDIDA
Rapporteur
A.CHECROUN
membre
C.BADJI
membre
G.LEVY

---

L'université n'entend donner aucune approbation, ni improbation aux
opinions émises dans les thèses: ces opinions doivent être considérées
comme propres à leurs auteurs.

---

REMERCIEMENTS
J'exprime toute ma gratitude envers le Professeur Gérard LEVY qui a dirigé
mes travaux. Il a été d'une disponibilité entière et ne m'a pas ménagé son soutien
tout au long de ce travail.
Je remercie également le Professeur Charles BERTHET qui m'a fait l'honneur
de présider le jury.
Je remercie les Professeurs Guy BOULAYE et Edmond FEDIDA qui ont bien
voulu être les rapporteurs de cette thèse.
Le Professeur Alain CHECROUN m'a accueilli dans son laboratoire tout le
temps qu'a duré mon travail et a accepté de participer au jury. Qu'il soit assuré de
mes sincères remerciements.
Je remercie le Professeur Chérif BAD~II qui a accepté de participé au jury.
Je n'oublie pas mes amis du Laboratoire CERIA avec j'ai passé toutes ces
longues années notamment Mona, Hugo, Romel, Richard, Tano,Tidiane Seck et
aussi mes amis de toujours que sont Martial, Ahmet, Tidiane Sow, Ibrahima, Pape
Fall. Je remercie aussi les amis du C.R.I.O pour leur constante disponibilité en
particulier MM Loret, Jean-Louis, Didier, Roland, Olivier etc...

---

i
CHAPITRE 1
INTRODUCTION ET MOTIVATION
1
1.1 RAPPELS
.
1.2 LES CCURBES REMPLISSANT L'ESPACE
2
1.2.1 La courbe de Peano
2
1.2.2 La courbe de Hilbert
6
1.2.3 Autres courbes
7
1.2.3.1. La courbe de Sierpinski
7
1.2.3.2 Code de Gray
7
1.2.3.4 Courbes fractales
8
1.2.3.5 Cas particuliers
9
1.3 APPLICATION DES COURBES DE PEANO
9
1.3.1 Transmission des données
9
1.3.2 Optimisation mathématique .;
10
1.3.3
Classification des données
11
1.3.4 Affichage de fonctions
12
1.3.5 Clustering
13
1.3.5.1 Bases de données spatiales ou multidimensionnelles
13
1.3.5.2 Hachage multiclé
15
1.3.6 Traitement d'images
16
1.3.7 Recherche opérationnelle
17
1.3.8 Compression des données
17
1.4. PLAN DE TRAVAIL ET ANALYSE DES PARTIES
18
1.4.1 Motivation
18
1.4.2 Analyse des parties
19
Chapitre2
ETAT DE L'ART DANS LE CLUSTERING
20
2.1 INTRODUCTION
20
2.2 Les travaux d'Orenstein
20
2.3 Les travaux de Faloutsos
22
2.4 Les travaux de Yagadish
25
l

---

i i
2.5 Conclusions
28
Chapitre 3 GENERATEURS DE COURBES DE PEANO-HILBERT..
..
3.1 NOTATIO~jS ET DEFINITIONS
29
3.1.1 Ordre lexicographique:
29
3.1.3.0rdre de Peano-Hilbert:
31
3.2 Transformations qui conservent l'ordre de Gray ou la forme de Gray:
31
3.2.1 Transpositions, permutations:
31
3.2.2 Complémentations:
32
3.3.Transformations qui conservent l'ordre ou la forme de Peano-Hilbert:
32
3.3.1 Transpositions, permutations:
33
3.2.2 Complémentations:
33
3.3.3 Remarques:
34
3.3.4 Produit cartésien "collé"
35
3.3.5 Conditions de raccordement (ou de continuité) :
36
3.3.6 Construction récursive d'un OPH sur Bn,m:
38
3.3.7 Détermination des t[r],q[r]pour n quelconque >1, et 1= 1
41
3.3.8 Détermination des transformations conservant la forme de Peano-
Hilbert pour 1= 1
3.3.9 Détermination des transformations qui conservent la forme de Peano-
Hilbert pour 1>1
43
3.3.10 Conclusion:
:
44
Chapitre 4 CLUSTERING EN DIMENSION 2
.45
4.1 PRELIMINAIRES
45
4.1.1 Position du problème
45
4.1.2 Algorithme
45
4.1.3 Conditions de l'expérimentation
.47
4.1.3.1 Choix d'une distribution
47
4.1.3.2 Dépendance par rapport à la forme
.48
4.2 COMPORTEMENT DU NOMBRE DE CLUSTERS ENFONCTION DE LA
i i

---

i i i
TAILLE DE LA BASE, CELLEDE LA FENETRE ETANT CONSTANTE
.48
4.2.1 Motivation
48
4.2.2 Expérimentations
48
4.2.3 Théorèmes
64
4.2.3.1 Expérience
64
4.2.3.2 Proposition
66
4.2.3.3 Proposition
67
4.2.3.4 Proposition
67
4.2.3.5 Proposition
68
4.2.3.6 Remarque:
68
4.2.3.7 Proposition
68
4.2.3.8 Proposition
69
4.2.4 Analyse du cas le plus favorable
69
4.2.4.1 Motivation
69
4.2.4.2 Expérimentations
69
4.2.4.3 Résultats
75
4.2.5 Analyse du cas le plus défavorable
76
4.2.5.1 Motivation
76
4.2.5.2 Expérimentations
76
4.2.5.3 Résultats
80
4.2.6 Comportement du nombre moyen de clusters par taille de fenêtre
80
4.2.7 Comportement du nombre moyen d'enregistrements par cluster
81
4.2.7.1 Motivation
81
4.2. 7.2 Expérimentations
81
4.2.8 Pertinence de la distance
83
4.3 COMPORTEMENT DU NOMBRE DE CLUSTERS EN FONCTION DE LA
TAILLE DE LA FENETRE, QUAND LA TAILLE DE LA BASE EST
CONSTANTE
84
4.3.1 Motivation
84
i i i

---

iv
4.3.2 Expérimentations
84
4.3.3.Théorème
86
4.4 CONCLUSION
86
CHAPITRE 5 CLUSTERING EN DIMENSION N > 2
88
5.1.INTRODUCTION
88
5.2.CLUSTERING EN DIMENSION 3
88
5.2.1.COMPORTEMENT DU NOMBRE DE CLUSTERS EN FONCTION DE LA
TAILLE DE LA BASE
88
5.2.1.1 Résultats expérimentaux
88
5.2.1.2
Remarque
93
5.2.1.3 Propositions
93
5.2.1.3.1 Proposition
93
5.2.1.3.2 Proposition
94
5.2.1.3.3 Proposition
94
5.2.1.3.4 Proposition
94
5.2.2.1 Résultats expérimentaux
95
5.2.2.2 Remarque
95
5.2.2.3 Proposition
95
5.3.CLUSTERING EN DIMENSION 4
95
5.3.1.COMPORTEMENT DU NOMBRE DE CLUSTERS EN FONCTION DE LA
TAILLE DE LA BASE
96
5.3.1.1 Rèsultats expérimentaux
96
5.3.1.2 Propositions .. '"
98
5.3.1.2.1. Proposition
99
5.3.1.2.2.
Proposition
99
5.3.1.2.3.
Théorème
99
5.3.2.COMPORTEMENT DU NOMBRE DE CLUSTERS EN FONCTION DE LA
TAILLE DE LA FENÊTRE QUAND LA TAILLE DE LA BASE EST
iv

---

v
CONSTANTE
99
5.3.2.1 Résultats expérimentaux
99
5.3.2.2 Remarque
100
5.3.2.3 Théorème
100
5.4.CLUSTERING EN DIMENSION
N > 4
100
5.4.1.COMPORTEIVIENT DU NOMBRE DE CLUSTERS EN FONCTIOf\\1 DE LA
TAILLE DE LA BASE
100
5.4.2.COMPORTEMEI\\JT DU NOMBRE DE CLUSTERS EN FONCTION DE LA
TAILLE DE LA FENÊTRE
101
5.5 CONCLUSION
101
chapitre 6
CONCLUSIONS ET PERSPECTIVES
102
ANNEXE
104
Bll/OGRAPHIE
113
v

---

CHAPITRE 1
INTRODUCTION ET MOTIVATION
1.1 RAPPELS
Tout au long de ce travail, nous utiliserons un vocabulaire que nous préférons
définir dès maintenant. Le traitement de l'information c'est-à-dire l'informatique consiste,
pour une bonne part, à stocker et à manipuler des données. De nos jours, on stocke
celles-ci
principalement sur des disques magnétiques après les avoir structurées en
enregistrements physiques. Un fichier est une collection d'enregistrements de même
nature. Le concept de base de données est apparu pour exploiter les liens entre les
fichiers
c'est-à-dire
leurs
éléments
communs.
Après
les
bases
de
données
hiérarchiques, puis réseaux, il y eut les bases relationnelles et aujourd'hui les bases
orientées objet. Ce sont ces deux dernières qui nous préoccupent.
Un enregistrement est composé d'un ou plusieurs champs ou attributs. La clé
d'accès d'un enregistrement est le ou l'ensemble des champs qui permettent d'identifier
totalement celui-ci c'est-à-dire de calculer son adresse physique sur le disque. Les
opérations
sur
les
données
sont
des
consultations,
mises-à-jours,
insertions,
interrogations ou requêtes, suppressions etc... "est
alors fondamental d'avoir
de
bonnes méthodes de stockage et d'accès aux données contenues dans les fichiers pour
rendre efficaces ces opérations. Ces méthodes doivent tenir compte de l'organisation
physique des disques magnétiques sur lesquelles sont stockés les fichiers. Parce que
trop volumineux, une base de données ne peut tenir toute entière en mémoire centrale
où se font les traitements. Donc elle est stockée sur un disque (mémoire secondaire) et
une partie seulement des données peut être amenée en mémoire centrale pour y être
traitée. En général l'unité de transfert entre la mémoire centrale et le disque est la page
qui est un bloc physique de taille fixée par le constructeur. Il y a donc des accès-disques
fréquents. Ceux-ci sont très coûteux parce que le processeur reste inactif le temps que la
donnée cherchée soit disponible. Dans l'état actuel de la technologie
des micro-
ordinateurs par exemple, un accès-disque se fait en 12 millisecondes (dans le meilleur
des cas) alors qu'un traitement en mémoire centrale prend 70 nanosecondes. Le rapport
est de l'ordre de 10-5 au mieux. Le même rapport se retrouve au niveau des autres
systèmes (mainframes, mini-ordinateurs, stations de travail). " faut donc organiser les
données de façon que le nombre d'accès-disques soit le plus petit possible.

---

2
Un disque est constitué de blocs. Chaque bloc a un nombre fixe de pages, chaque
page ayant un numéro ou adresse permettant de la repérer. "existe
des méthodes
d'accès directes basées sur le hachage et des méthodes
indexées basées sur les
arbres.
Le hachage
Le principe de la méthode de hachage est le suivant:
-on répartit les enregistrements dans des blocs numérotés
-chaque bloc peut contenir au plus N enregistrements(N entier fixé >1)
-une fonction de hachage h attribue à toute clé un numéro de bloc où sera stocké
l'enregistrement correspondant.
Cette méthode d'accès direct a été intensivement étudiée du fait de son efficacité et
comportent plusieurs variantes(hachage dynamique, virtuel, linéaire, digital etc..). On
peut consulter Knuth[1973], Fagin[1979], Larson[1978], Litwin[1980] etc....
Les fichiers indexés
C'est le principe utilisé dans les dictionnaires. Pour chercher le mot poteau par
exemple on va directement à la page où commencent les mots débutant par la lettre p.
Puis parmi celles-ci vers celles qui contiennent les mots ayant 0 comme deuxième lettre.
Et ainsi de suite. Ainsi pour chercher un enregistrement on consulte d'abord un espace
intermédiaire appelé fichier d'index ou plus simplement index. L'index a une structure
d'arbre. Les clés couplées avec leur adresse de page sont stockées aux noeuds de
l'arbre. Plusieurs structures d'arbre ont été étudiées(arbres binaires, m-aires, B-arbres,
etc...). On peut consulter Knuth[1973], Bayer-Mac Creight[1972].
1.2 LES COURBES REMPLISSANT L'ESPACE
1.2.1 La courbe de Peano
En 1890 le mathématicien italien
Peano[1890] exhiba une courbe ayant des
propriétés étonnantes. C'était une application de la droite réelle sur le plan, continue,
bijective. A tout point de la droite, elle fait correspondre un point et un seul du plan. La
courbe passe une seule fois par tout point du plan, "remplissant" celui-ci. D'où le nom de
courbe
remplissant l'espace. Peano la construisit de la façon suivante. La droite est
2

---

3
ramenée sans perte de généralité au segment [0,1] et le plan au carré [0.1]2. Si b est un
entier pris comme base de numération. tout nombre rationnel p de [0,1] peut s'écrire
sous la forme
Par convention on écrira
P=t1 t2t3..........
et
Pm=t1t2 .......tm sera appelée l'approximation d'ordre m de p
Soit (x,y) l'image de p E [0,1]2 avec
x=D<jb-i = x1x2"".et
y = ~Yib-i = Y1Y2.... alors les valeurs de xm et Ym pour toute valeur d'approximation m
sont données par
x = kX1 +"".+xm-1+y1+.".ym-1 t
m
2m-1
r,
r h r
r,
1
1
1
1
L.. ~
L.. ~
L.. ~
r-
i1
r~
1
1
1
...J
L
.J
r r,
r :1
r r,
1
1
1
1
L_
.....J
L ~
L..
Fig.1 Courbe de Peano
Fig.2 Courbe de Peano
étape 1
étape 2
Fig.3 Courbe de
ïPeano
étape 3
3

---

4
Bien entendu tout ceci est généralisable à tout espace de dimension n quelconque.
en particulier au cube-unité [0.1]3 qu'on peut aussi construire
Fig4 Courbe de Peano
en dimension 3
étape 1
On constate avec intérêt que le procédé de construction géométrique est récursif. C'est
le même schéma de base qui revient à chaque étape. subissant des transformations
géométriques comme des rotations et/ou des symétries. Ce qui permet de développer
des algorithmes récursifs pour tracer la courbe.
Bien entendu
on peut. de la même façon. construire les courbes de Peano avec
b=5,7 ..... etc..... c'est-à-dire avec tout entier impair supérieur à 1.
Fig.5 Courbe de Peano avec b=5
étape 1
Quand à l'application réciproque de la courbe de Peano, elle projette
de façon
4

---

5
univoque l'espace multidimensionnel Rn sur la droite R. On procède par approximation.
L'image du point rationnel
(xm'Ym) sera le rationnel Pm que l'on peut calculer en
fonction des xi et Yi'
20 21 26 27 32 33 74 75 80
'"1
3
..
8
19 LL 25 28 31 34 73 76 79
18 23 24 14::::1 30 35 72 77 78
17 12 11 42 41 36 71 66 65
4
1
7
16 lJ 10 43 40 ,JI 70 67 64
15 14 9 44 39 38 69 68 63
2
3
8
45 50 51 56 57 62
1)
5
6
1
4
7
46 49 52 55 58 61
0
5
6 47 48 53 54 59 60
Fig.6 Balayage de Peano
Fig.7 Balayage de Peano
étape1
étape 2
En fait, chaque point (xm,Ym ) du carré représente un hypercube de sommet minimal
(xm,Ym) et de coté b-m. Ainsi donc le carré est divisé en b2m hypercubes et on peut dire
Il
.
que chaque hypercube a pour image un point
Pm= L t. b-1 . Celui-ci peut être
1 1
Il
.
transformé en entier L t. b 1 . Ainsi on a attribué à chaque hypercube un numéro unique
1 1
ou adresse. On a donc obtenu un parcours ordonné du carré d'où le nom de balayage
de Peano. Le balayage de Peano a deux propriétés intéressantes. D'abord il applique
Rn sur R où il est généralement plus facile de résoudre les problèmes. Ensuite il est
quasi-continu c'est-à-dire que son ensemble de discontinuité est de mesure nulle. Plus
concrètement on peut affirmer que deux hypercubes voisins dans le carré auront des
numéros "voisins". On dit que deux hypercubes sont voisins si ils ont un coté commun
(selon les axes) alors que deux numéros sont voisins s'ils sont consécutifs. Un
hypercube dans le carré peut avoir 4 voisins mais son image a au plus deux voisins sur
le segment. Il y a donc deux
de ses
voisins qui sont au moins à une "distance"
supérieure à 1 mais on peut espérer que celle-ci ne soit pas trop importante. Ceci permet
donc de ramener un problème dans Rn en un problème dans R. En trouvant une solution
5

---

6
dans R, on espère que son image sur la courbe de Peano n'est pas loin de la solution
cherchée. C'est ce principe de localité ou propriété de conserver les distances qui va
être massivement utilisé dans divers domaines de l'informatique.
1.2.2 La courbe de Hilbert
Un an après Peano, le mathématicien allemand Hilbert[1891] découvrit un second
exemple de courbe remplissant l'espace. Bien qu'il n'en donna qu'un procédé de
construction géométrique, celui-ci est récursif et simple.
1
1
1
1
fig.8 courbe de Hilbert
fig.9 courbe de Hilbert
fig. 10 courbe de Hilbert
étape 1
étape 2
étape 3
21
22
25
2B
37
38
41
42
20 23
24
27
36
39
40
43
19
18
29
28
35
34
45
44
5
6
9
la
16
17
30
31
32
33
46
47
2
15 12 11
10
53
52
4
7
8
11
51
48
14
13 8
9
54
55
50
49
:3
2
13
12
1)
3
1
2
7
6
57
56
62
0
1
14
15
0
3
4
5
58
59
""60 63
Fig.11 balayage de Hilbert
Fig .12 balayage de Hilbert
Fig.13 balayage de Hilbert
étape1
étape2
étape3
Pour la courbe de Hilbert la base de numération est 2. Butz[1969] exhibe un
algorithme de construction analytique
de cette courbe. Pour l'afficher
sur écran
d'ordinateur ou tracer sur papier, énormément d'articles ont été proposés dans la plupart
des
langages
informatiques
standards.
Citons
entre
autres
Goldslager[1981],
Cole[1983]. Witten-Wyvill[1983], Fisher[1986], Griffiths[1985][1986], Palmer[1986],
Yagadish[1990],etc ..(voir bibliographie).
La simplicité de sa construction, aussi bien analytique que géométrique, a fait le
succès de la courbe de Hilbert sans compter qu'elle a
b=2
pour base de numération
ce qui fait qu'on manipule que des bits.
Moore[1900] étudia des propriétés mathématiques des courbes de Peano et Hilbert
(nous dirons dorénavant courbes de Peano-Hilbert).
6

---

7
1.2.3 Autres courbes
1.2.3.1. La courbe de Sierpinski
Sierpinski[1912] donna un
troisième exemple de courbe remplissant l'espace
ayant les mêmes propriétés que les précédentes. Mais contrairement à celles-ci sa figure
de base contient des segments non parallèles aux axes.
1.2.3.2 Code de Gray
En électronique le code de Gray[1957] est bien connu. Pour un entier m donné il
s'agit de coder en nombres binaires les entiers compris entre a et 2m-1 de telle sorte
deux nombres consécutifs diffèrent seulement par un bit de position. Par exemple pour
m=4, on peut avoir:
décimal
Gray
binaire
o
0000
0000
0001
0001
2
0011
0010
3
0010
0011
4
0110
0100
5
0111
0101
6
0101
0110
7
0100
0111
8
1100
1000
9
1101
1001
10
1111
1010
11
1110
1011
12
1010
1100
13
1011
1101
14
1001
1110
15
1000
1111
Cette dernière propriété est aussi vérifiée par les courbes de Peano et de Hilbert. On
7

---

8
peut construire aussi bien une courbe de Gray qu'un balayage de Gray.
1
Fig.14 Courbe de Gray
Fig.15 Courbe de Gray
étape 1
étape 2
1.2.3.4 Courbes fractales
Les courbes fractales sont des courbes qui ont la même figure de base quelque soit
l'échelle d'observation. Elles
ont été introduites par Mandelbrot[1975][1977]. Les
courbes de Peano-Hilbert peuvent être vues comme des courbes fractales élémentaires
puisque c'est la même figure
de base
qui revient à n'importe quelle degré
d'approximation.
1.2.3.5 Cas particuliers
1
1
fig.16 Figure de base de la courbe de Hilbert 2 x 4
1.3 APPLICATION DES COURBES DE PEANO
1.3.1 Transmission des données
Ce fut Bially[1969] qui, le premier, utilisa les courbes de Peano-Hilbert dans le
domaine de la transmission des données. Depuis Shannon[1948], le principe de la
théorie de l'information
est bien établi. Après échantillonnage du signal d'entrée, on
8

---

9
obtient des signaux uniformément espacés dans le temps; chacun d'eux étant supposé
être un intervalle de [0,1]. La largeur de bande de chaque signal est égal à T/2 ' où Test
le temps s'écoulant entre deux signaux. On regroupe alors tous les signaux par sous-
ensembles disjoints de cardinal N. Ainsi chaque sous-ensemble peut être vu comme un
élément de [0,1]N . Au lieu de transmettre N données on va en transmettre une seule
en utilisant un balayage de Hilbert de [0,1]N vers [0,1]. On espère alors récupérer les N
signaux initiaux à la sortie du canal de transmission grâce à la quasi-continuité du
balayage. Bially réalise un dispositif basé sur "les diagrammes d'état" qui sont des
transformations permettant de donner les images par le balayage pour toute dimension
n et tout ordre d'approximation m. La figure ci-dessous est tiré de l'article de Bially.
Fig.17 Diagramme d'état pour la courbe de Hilbert pour n=2 et m=2
1.3.2 Optimisation mathématique
On considère le problème suivant: trouver x E [0,1]n tel que f(x)
::; a quand les
méthodes habituelles sont
inapplicables.
Butz[1968][1969]
proposa
d'utiliser une
procédure de "recherche implicite exhaustive" utilisant les courbes de Peano-Hilbert.
On pose X={x E
[0,1]n tel que f(x) ::; °}qui peut être éventuellement vide. On
considère la courbe de Hilbert (ou
Peano) h:r E [0,1 ]-------->x E [0,1]n
continue et
bijective. Elle vérifie la propriété suivante(Butz[1 968]):
1/ 6 xii::;
M Il M11 1/n .
Soit U ={x E [0, 1]n tel que f(x) > o} alors on fait l'hypothèse suivante:
pour tout x'
E U ,on a :
9

---

10
0< fc(x')::; f(x')::; K(x') inf{I/X-X'llq tel que x EX} où f est continue sur U et non
nécessairement connue, K est continue définie sur U et satisfaisant:
O<K(x')::; L <x .
Butz prouve alors le résultat suivant:
si la suite { ri,xi } avec rO=O et xi=h(ri) est définie par
ri
si f(xi) ::; 0
alors si X est non vide la suite xi converge vers un certain 2S. dans X.
Si X est vide alors ri =1 pour un certain i fini et f(h(1» >0.
Grâce à l'hypothèse faite
on a :
pour tout i ,h(r)
E
U pour tout r < ri. Ainsi on peut évaluer f en chaque point de
[0,1]n sans faire de calcul. L'utilisation de la courbe de Hilbert a permis de ramener le
problème dans R. Comme application, Butz[1969] donna l'exemple suivant:
2
X, + x x
-1
~
2 3 - x4xs + Xs
x - x -
x X + x x
+1
~o
3
4
1 2
3 S
{
Xl
-X X
-x
x
+1
~o
1 3
2 x4 S
x +
x
x
-1
~o
4
2 x4 S
La solution x=(0.16406,0.80078,0.87500,0.85938,O.99609) est trouvée après 1721
itérations prenant un temps machine de 1.9 secondes.
Par contre on montre au bout de 1.153.835 itérations durant 15 minutes que le
système suivant n'a pas de solution.
=.5
=.5
{
=.5
Xs + x,x
=.5
3
x + X
2
s
=.5
1.3.3
Classification des données
Il s'agit de répartir une population en catégories homogènes, stables. C'est
un
problème
fréquent dans beaucoup
de domaines scientifiques (médecine, botanique,
10

---

11
reconnaissance des formes, intelligence artificielle, etc...). En classification automatique,
on dispose de plusieurs méthodes (par hiérarchie, par arbre, par partition, par typologie,
etc...), toutes
nécessitent le choix d'une mesure de ressemblance(voir Diday[cours
polycopié Université Paris-Dauphine]). Alexandrov[1978][1982] proposa, le premier,
une méthode basée sur le balayage de Hilbert qui n'utilisait pas les distances. Il sera
suivi par Simon-Quinquéton[1978], Berthod-Quinquéton[1981]. On procède ainsi.
Soit X=(x1 ,x2,
,xn) la représentation de n mesures d'un objet 0. La représentation
X est appelée aussi description ou forme initiale de 0. On veut identifier X c'est-à-
dire séparer l'ensemble Edes X en classes disjointes (partitions). Cette classification sera
plus rapide si on peut réduire la dimension n. On utilise alors un balayage de Peano-
Hilbert pour opérer cette réduction. On suppose que X est dans [0,1 ln. Celui-ci est
subdivisé en bnm hypercubes par un balayage d'ordre m de Peano ou Hilbert. Chaque
hypercube reçoit un numéro (c'est en fait une technique d'adressage). Ainsi toutes les
mesures xi se trouvant dans le même hypercube recevront la même adresse. Si, dans
un hypercube, le nombre et supérieur à un nombre fixé au départ, on éclate celui-ci et on
recommence. Les figures ci-dessous sont tirées de Berthod-Quinquéton[1981].
(2)
(0)
(0)
(5)
.?
Fig.18
fig.19
(2)
(0)
+ (0)
(0)
(0)
(0)
(0)
(0)
(0)
~n I~ ~l ~l
(1 )
(2)
(0)
(0)
~l) 1~l) or) ~l)
(0)
(2)
~l
(0)
~
-;; ~l
Fig.2D
fig.21
Etapes successives de classification
Remarquons que KanaJ et autres[1968], en reconnaissance des formes statistique,
11

---

12
avait proposé de modéliser une forme aléatoire binaire multidimensionnelle par une
chaîne de Markov le long d'une courbe de Peano. Ce n'est pas exactement un modèle
probabiliste multidimensionnel mais c'en est une bonne approximation grâce à la quasi-
continuité du balayage de Peano.
1.3.4 Affichage de fonctions
Le problème est de tracer, sur écran d'ordinateur par exemple, une fonction
f: Rn ------>R
quand
n------>1.
C'est un problème difficile. On pose 0=[0,1 Jn. Alors on subdivise 0 en N sous-
ensembles Ei disjointes' qui recouvrent 0 tels que f soit égale à une constante Cj
sur
chaque sous-ensemble Ej. Soit h une application qui transforme chaque élément Ei de
la partition en un intervalle li de R de façon que la longueur de chaque intervalle soit
égale au volume du sous-ensemble antécédent et que la réunion des li soit aussi un
intervalle de [0,1 J. Soit g une application définie sur la réunion des li ' g est égale à ci
sur chaque intervalle li; on a donc construit une fonction qui approxime f et qu'on peut
facilement afficher. La fonction h, en fait, n'est qu'un balayage de [0,1]n dans [0,1 J.
Patrick[1968] eut alors l'idée d'utiliser un balayage de Peano.
1.3.5 Clustering
1.3.5.1 Bases de données ,spatiales ou multidimensionnelles
Dans maintes applications on manipule des données complexes. C'est le cas, par
exemple, en cartographie, en conception de système VLSI, en robotique, en CAO,
etc... On parle de bases de données spatiales. C'est le cas des bases de données
géographiques, des bases de données temporelles, etc... La notion de donnée spatiale
diffère grandement d'une application à l'autre, surtout du fait de la dimension des
données.
En
effet,
les données
temporelles
sont
vues
comme
des
données
monodimensionnelles alors que les applications géographiques et la conception des
VLSI manipulent des données bidimensionnelles. Par contre les applications géologiques
nécessitent trois dimensions alors que la modélisation des solides en nécessitent quatre
pour
pouvoir détecter
les
interférences
entres
des
objets
tridimensionnels
en
mouvement. Dans certaines applications les objets sont continus alors que dans d'autres
ils sont discrets. Il y a donc une grande diversité de situations suivant les applications. Il
12

---

13
s'agit alors de trouver un modèle de donnée permettant d'implémenter tous les cas de
situation possible.
Différentes implémentations existent. Le modèle PDM (Orenstein-Manola[1988]) a,
par exemple, deux types de base de donnée: les entités et les fonctions. Une entité est
un objet-donnée qui signifie quelque chose d'individuel. La caractéristique d'une entité
est d'avoir une identité propre. Les entités qui ont des caractéristiques similaires sont
regroupées dans des collections dites
types d'entité. Les propriétés des entités, les
relations entre entités, et les opérations sur les entités sont uniformément représentées
dans le modèle PDM par des fonctions. Ainsi, pour accéder aux propriétés d'une entité,
ou aux relations de celle-ci avec d'autres entités, ou pour effectuer des opérations sur
cette entité, on doit évaluer une fonction ayant cette entité comme argument. Par
exemple, la fonction
population(CITE) ---------->INTEGER
permet d'accéder à la
valeur de l'attribut population d'une entité CITE. Les types d'entité peuvent être
subdivisés en sous-types, permettant ce qu'on appelle des hiérarchies de généralisation
(héritage de type). Au sommet de la hiérarchie de généralisation, les entités et les
fonctions sont des membres du type générique ENTITY. On dérive du type ENTITY un
type POINT-SET destiné à modéliser tous les types de données spatiales.
Les données spatiales sont modélisées par des abstractions mathématiques appelés
ensemble-points.
L'ensemble-point d'un objet est "ensemble des points dans
l'espace occupé par cet objet. Un ensemble-point est un membre du type POINT-SET.
Celui-ci est une spécialisation de du
type ENTITY qui introduit
une collection
d'opérateurs spatiaux tels que la réunion, l'intersection. la différence, ainsi que les
prédicats spatiaux comme le recouvrement, la contenance et la proximité.
Un
filtre
géométrique
alors
permet
l'approximation
des
objets
spatiaux
et
l'optimisation des requêtes de sélection spatiales. La représentation utilisée par le filtre
géométrique est conceptuellement une grille. Un ensemble-point n-dimensionnel(n-d)
dans un espace n-d est approximé en une grille n-d de cellules sur l'espace et en notant
celles qui contiennent une partie de l'ensemble-point
(voir figure ci dessous). Cette
approximation est conservative car l'objet approximé est entièrement contenu dans la
réunion des cellules avec lesquelles il a une intersection non vide.
13

---

14
D cellule dela grille
Il objet spatial
1::·:·....;:1
approximation conservalive
Fig.22
Approximation conservative d'un objet spatial
Dans une grille de résolution 2m x 2m
,chaque cellule est caractérisée par ses
Les xi
et
Yi
sont des bits. On choisit alors un balayage des cellules qui préserve
le mieux la proximité. C'est-à-dire que deux points voisins dans l'espace aient des
adresses voisines
dans l'ordre induit par le balayage. Ceci permet aux cellules
appartenant à un même objet d'être stockées sur la page en mémoire secondaire. On
peut ainsi retrouver l'objet en un nombre minimal d'accès-disques. C'est le principe du
regroupement ou clustering; celui-ci dépend donc essentiellement de la fonction de
balayage choisie. Un cluster est donc un groupe de cellules d'adresses consécutives
sur le disque. Ainsi toutes les cellules d'un même cluster peuvent se retrouver sur la
même page.
1.3.5.2 Hachage multiclé
On
peut
étendre
la
notion
de
hachage
fichiers
multiclé
Rothnie[1974],
Faloutsos[1985])
Chaque clé de l'enregistrement est hachée, puis on concatène les résultats obtenant
ainsi
l'adresse sur disque de l'enregistrement. Prenons l'exemple suivant dû à
Faloutsos[1988]
00
si x< "E"
01
si "E":sx<"L"
10
si "L"Sx<"S"
14

---

15
11
si "S"$)(
a
si y ~35
sinon
a
si w ~25 000
si w > 25 00
Donc l'enregistrement ("Smith",40,22000) a pour signature 1110 qu'il suffit de lire
dans le code voulu pour avoir l'adresse de la bloc de disque où se fera le stockage. Par
exemple 1110=14 en code binaire.
On dira que la bloc
n014 a pour signature
caractéristique 1110.
Les enregistrements répondant aux requêtes partiellement exactes comme par
exemple
Quels sont les noms des employés dont le salaire est égal 20000 et l'tJge à 50 ?
ont la forme suivante:??10 . Ils sont contenus dans les blocs ayant pour signatures
0010,0110,1010 et 1110 c'est-à-dire les blocs n02, 6,10 et 14.
Ainsi, des enregistrements qui n'ont que deux bits différents peuvent se retrouver
stockés dans des blocs très éloignées, nécessitant un effort important en nombre
d'accès-disques. Il faut tenter alors de faire en sorte qu'on puisse passer d'un bloc au
suivant en changeant seulement un bit de position. On utilise alors un codage de Gray,
ou de Hilbert, ou de Peano. En effet, dans ceux-ci on passe d'un nombre au suivant en
changeant seulement un bit de position.
Dans ce cas, les enregistrements similaires
seront stockés dans des blocs voisins.
1.3.6 Traitement d'images
En traitement d'images l'espace est discrétisé en éléments appelés pixels. Chaque
pixel reçoit une couleur. Une image (binaire) est donc un tableau de pixels noirs sur un
15

---

16
fond de pixels blancs par exemple. C'est donc une région de l'espace. Les pixels noirs
reçoivent le code 1 et les blancs le code O. Pour stocker une image, on crée par
décompositions successives de la région une structure de données hiérarchique appelée
quadtree. Par un balayage de Peano-Hilbert, chaque pixel reçoit alors une adresse.
Ainsi l'image est complètement reproductible. Voir Laurini[1985] sur le traitement des
images et le codage des couleurs et Samet[1984] pour un point exhaustif sur les
quadtrees.
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
a
, ,
a
a
a
a
1
1
a
a
a
a
1
1
1
1
, , , , ,
a
a
a
, ,
a
a
, 1 1 1
,
a
a
,
1
1
a
a
, ,
a
a
1
a
a
a
a
b
c
d
fig.23 a:région; b:tableau binaire; c: blocs; d:quadtree correspondant
Evidemment, ici aussi, le numérotqge des pixels joue un rôle fondamental pour le
stockage des images. Plus le regroupement est efficace, plus l'accès est rapide.
1.3.7 Recherche opérationnelle
Le problème du voyageur du commerce modélise beaucoup de problèmes en
recherche opérationnelle. Il s'agit de construire un circuit de longueur minimale passant
par N points donnés. Bartholdi-Platzman[1982] ont utilisé une courbe remplissant
l'espace pour construire un algorithme
en O(NlogN) alors que même dans le plan ce
problème est NP-complet. L'algorithme est le suivant.
Soit
f: [0,1]----------->[0, 1]2 une courbe remplissant l'espace telle que Iim
f(t)=f(O)
lorsque t tend vers 1. Quand t varie de 0 à 1 , la courbe passe alors par les N points du
16

---

17
plan [0,1]2. On décide donc de visiter les N points du plan dans l'ordre où ils apparaissent
le long de la courbe. On suppose qu'il existe une fonction
g sur [0,1] ,avec g(O)=O et g(u)=g(1-u) telle que Ilf(t) -f(t')11 $ g(lt-t'l) où Il . Il désigne
la distance utilisée dans le plan. Bartholdi et Platzman exhibent une courbe remplissant
l'espace assez proche de la courbe de Sierpinski et vérifiant les hypothèses nécessaires.
1.3.8 Compression des données
Ce domaine est devenu de nos jours une question d'une grande importance. D'abord
les fichiers deviennent volumineux nécessitant des moyens de stockage coûteux dont
les capacités ont, de surcroît, des limitations physiques(disques, bandes magnétiques,
etc). Ensuite le développement du multimédia (images animés, son, etc...) qui manipule
et échange des fichiers de données au volume prohibitif est bloqué, entre autres, par
l'insuffisance des capacités actuelles de stockage. Alors on est arrivé à la conclusion
qu'il faut une solution logicielle à ce problème c'est-à-dire compresser les fichiers. Ceci
explique le fait qu'énormément de chercheurs travaillent dans ce domaine et, bien sûr, il
existe une grande variété de techniques de compression de fichiers. Considérons celle
dite de la différentiation. Soit un fichier F où les enregistrements X ont plusieurs
champs X=(x1 ,x2,
,xn) E [0,1]n On range les enregistrements de la façon suivante.
On range d'abord le premier enregistrement, ensuite du second on ne stocke que les
champs qui diffèrent de ceux du premier enregistrement. Et ainsi de suite..... Si les
enregistrements ont plusieurs champs similaires alors le fichier obtenu sera bien plus
petit que le fichier de départ. On constate dès lors que "ordre initial des enregistrements
est décisif. Plus deux enregistrements successifs auront des champs semblables, plus la
compression sera meilleure. Ernvall[1984], Richards[1986] eurent l'idée d'utiliser l'ordre
induit par le code de Gray. On sait que, dans cet ordre, deux éléments successifs ne
diffèrent que par un bit de position. Supposons qu'on a 2m enregistrements, le fichier F a
donc n·2 m champs mais en le compressant F n'aura plus que n+2m -1 champs.
1.4. PLAN DE TRAVAIL ET ANALYSE DES PARTIES
1.4.1 Motivation
Les bases de données standards du marché manipulent des données de type
numérique ou chaînes de caractères. Or, dans beaucoup de domaines de la vie
17

---

18
courante, on a affaire à des données plus complexes; on parle alors de données
spatiales. Suivant les domaines considérés, on a des données à une, deux, trois, voire
quatre dimensions. Et,aujourd'hui , il faut envisager des données d'ordre supérieur.
On peut alors définir la plupart des opérations habituelles nécessaires à la gestion
d'une base de données. 1/ se pose alors le problème de la recherche d'un objet c'est-à-
dire les cellules du plus petit rectangle le contenant. Il faut alors regrouper ces cellules
sur le disque de façon que le système puisse les accéder en un nombre minimum
d'accès-disques. Ce regroupement ou clustering dépend donc de la façon d'adresser sur
le disque les cellules de base de l'espace. Pour faire ceci,
Orenstein[1986],Faloutsos[1988],Yagadish[1990] ont eu l'idée d'utiliser des courbes
remplissant l'espace, principalement les courbes de Hilbert, Gray et z-ordre. Mais ils ne
menèrent des expérimentations qu'en dimension 2. De plus, les résultats observés n'ont
pas été démontrés analytiquement.
Nous nous proposons d'abord d'inclure dans la liste des courbes étudiées celle de
Peano qui, nous semble-t-il, a été négligée parce qu'elle utilise le chiffre 3 comme base
de numération au lieu de 2.
Ensuite nous menons des expérimentations pour toute
dimension supérieure à 2. Enfin, nous prouvons mathématiquement tous les résultats
obtenus.
Il est d'un grand intérêt
d'étudier le comportement des différentes courbes quand la
dimension devient grande. Orenstein[1988] a abouti à la nécessité d'étudier le
regroupement dans des espaces de dimension supérieure à 2.
1.4.2 Analyse des parties
Dans le chapitre 2, nous faisons le tour de ce qui a été fait jusqu'à
présent en ce qui
concerne le clustering dans les bases spatiales.
Dans le chapitre 3 nous revenons sur les courbes remplissant et leur génération.
Nous exhibons une procédé qui permet d'obtenir les courbes de Peano-Hilbert pour toute
dimension et toute base de parité à partir de la courbe de Gray. Ce résultat permet non
seulement l'unification de toutes ces courbes mais aussi montre le lien entre les
propriétés analytiques et géométriques de celles-ci.
18

---

19
Dans le chapitre 4, nous étudions le clustering en dimension 2.
Dans le chapitre 5, nous étudions le clustering en dimension 3, puis en dimension 4,
et enfin nous généralisons à toute dimension supérieure à 4.
Enfin, le chapitre 6 sera notre conclusion et parlera des perspectives de recherche.
19

---

Chapitre2
ETAT DE L'ART DANS LE CLUSTERING
2.1 INTRODUCTION
Les algorithmes de clustering ont été utilisés dans beaucoup de
domaines, notamment en analyse des données, dans l'étude des R-arbres,
en traitement d'images, etc...Nous nous intéressons pour notre part au
clustering des données dans les bases spatiales.
Trois
auteurs
ont
étudié
intensivement
ce
domaine.
Ce
sont
Orenstein[1984][1986][1988],
Faloutsos[1984][1986][1989]
et
Yagadish[1990].
2.2 Les travaux d'Orenstein
C'est Orenstein[1986] qui eût, le premier, l'idée d'utiliser une
courbe
remplissant l'espace dans les algorithmes de clustering dans les bases de
données spatiales.
Il
a introduit la courbe remplissant l'espace appelée courbe z-ordre.
fig .24 z-courbe
fig .25 z-courbe
étape 1
étape 2
6
8
14
16
2
4
5
7
13
15
2
4
10
12
3
1
3
9
11
fig.26 Balayage z-ordre
fig .27 Balayage z-ordre
étape 1
étape 2

---

\\
21
Remarquons les "sauts" de la z-courbe. Pour passer d'un point à un
autre, on doit parfois changer plus de deux bits à la fois.
Le clustering est d'abord abordé de la façon suivante. Les données sont
les points du plan ramené sans perte de généralité à [0,1]2. Pour chaque
ordre d'approximation m, on a 22m points de coordonnés (x,y) avec
X=X1X2....Xm et y=y1y2.....ym et d'adresse D dans le balayage z-ordre des
points. Traiter une requête par intervalles revient à déterminer l'ensemble
{(x, y) tels que
a~x<b etc~y<d;a,b,cetdE[0,1]2}.
On dit que la requête par intervalles est une fenêtre [a,b[ x[c,d[.
Evidemment, plus les adresses des points de la fenêtre seront proches,
plus la recherche sera rapide. D'où l'intérêt à effectuer un clustering
préalable des données.
Orenstein effectua des calculs expérimentaux dans les conditions
suivantes. Un S+-arbre permet de stocker les points de la base ordonnés
par le z-ordre. La capacité d'une page de disque est de 20 points. On
génère 5000 points pour chaque expérience et trois séries d'expériences
sont menées. D'abord les données sont uniformément distribuées dans tout
l'espace, ensuite elles sont uniformément distribuées le long de la diagonale
x=y et, enfin, elles sont regroupées en petits groupes de 100 points chacun.
Pour chaque série, des requêtes de formes rectangulaires variées sont
exécutées
en cinq positions aléatoires. On mesure principalement le
nombre de pages accédées d'une part et, d'autre part, le nombre de points
"pertinents"( i.e appartenant à la région de recherche) par page accédée.
Les constatations suivantes ont été faites:
_ le nombre de pages accédées est en O(kN) où k est la surface de la
région de recherche normalisée par la surface totale de l'espace et N est le
nombre de pages de la sélection. En d'autres termes, le nombre de pages
accédées dépend de la taille de la requête.
_ les requêtes de forme carrée connaissent de meilleurs résultats que.
celles de forme rectangulaire quelconque.
21

---

22
Ensuite Orenstein[1988] aborde le domaine du clustering dans le cadre
des bases spatiales. Il n'utilise que le balayage z-ordre. Aucune expérience
pratique n'est effectuée dans ce dernier cas..
2.3 Les travaux de Faloutsos
Faloutsos[1 986][1 988] utilise d'abord le c1ustering dans le cadre du
hachage multiclé pour adresser les points d'un espace multidimensionnel
sur les pages de disque. L'utilisation du code de Gray permet de regrouper
ensemble les points similaires sur des pages voisines
de façon plus
efficace que le code binaire. Ceci permet de traiter de manière plus efficace
les requêtes partiellement exactes.
Ensuite, Faloutsos[1989] reprend
les résultats d'Orenstein sur le
clustering
concernant
les
requêtes
par
intervalles dans
un
espace
multidimensionnel. Mais au lieu du balayage z-ordre, il utilise l'ordre induit
par le balayage de Hilbert. en faisant l'hypothèse que celui-ci est meilleur
car il n'a pas de saut et donc préserve mieux les distances. Les trois séries
d'expériences qu'il effectue vont dans le même sens.
Dans
Faloutsos[1990],
une
nouvelle
méthode
dite
double
transformation (DT) est proposée. Celle-ci veut concilier les avantages de
deux autres méthodes: celle des fichiers-grille d'abord et celle des courbes
remplissant l'espace ensuite.
Dans les fichiers-grille(Hinrichs-Nievergelt[1983]) tout point de l'espace
n-dimensionnel est transformé en point d'un espace 2n-dimensionnel.
La méthode DT se fait en trois étapes.
•Tout objet
de l'espace n-dimensionnel (espace initial)est représenté
par le plus petit hypercube le recouvrant
. Cet hypercube est transformé en un point de l'espace 2n-dimensionnel
(espace intermédiaire). C'est la première transformation.
22

---

23
. Une courbe préservant les distances est utilisée pour adresser ce point
sur
un
espace
1-dimensionnel
(espace final).
C'est
la
seconde
transformation.
Pour n=1, l'image de [0,1] par la première transformation n'est pas le
carré [0,1]2 mais le triangle {(O,O),(O, 1)(1 ,a)}. Il est nécessaire d'adapter les
courbes remplissant l'espace aux triangles. Ces versions particulières sont
appelées courbe tri-Hilbert et courbe tri-z-ordre.
~ ,~, ::.
:••••••....... 1:
~
.......•••................•........
>/
.........................1
1········
:
:
:
;
::
:
;
.
1
~ :••...
_. _.... _.. - ..
- .. -_
~
,
'.~
• • • • • • • • • • • • • • • • • • • • • • • • • • • • 0(
..
.
.
fig.28 courbe tri-Hilbert
fig.29 courbe tri-z-ordre
En s'intéressant d'abord au nombre de clusters, les résultats suivants
sont observés, pour un espace initial 1-dimensionnel et pour tous les cas de
requêtes par intervalles possibles.
lordre m
~Taille oTri-Hilbert ~ Tri-z-ordre
1
1
2'2
1,00
1,00
2
4'4
1,20
1,30
3
8'8
1,78
2.33
4
16'16
3,06
4,79
5
32'32
5,70
10,00
6
64'64
11,02
20,59
fig.30
La courbe tri-Hilbert est plus efficace que la courbe tri-z-ordre
Ensuite
des
calculs
expérimentaux
concernant
pour
mesurer
concrètement le nombre d'accès-disque sont effectués dans les conditions
suivantes. Un générateur de nombres pseudo-aléatoires permet de créer
des segments de droite dans l'espace initial de façon que leurs transformés
soient uniformément distribués dans l'espace intermédiaire. Les points de
l'espace intermédiaire sont adressés sur l'espace final par les balayages tri-
23

---

24
Hilbert et tri-z-ordre. Ces adresses sont stockées dans les noeuds d'un S+-
arbre.
Chaque requête dans l'espace initial est transformé en un ensemble de
requêtes dans l'espace final, et on mesure alors le nombre d'accès-disque
que requiert le S+-arbre.
On suppose que:
.Ia taille d'une page est de 128 octets
.Ies noeuds internes ont 15 entrées
.Ies feuilles ont au plus 4 clés.
r
r
On évalue alors le nombre t=t nombre de pages lues/t nombre de
1
1
points pertinents
q,r
Tri-Hilbert
Tri-z-ordre
1=52,L=700
1=55,L=691
0,30
0.697
0.790
1.15
0,668
0,744
2,10
0,669
0,683
3,20
0,662
0,676
4,20
0,676
0,689
fig.31
Nombre de pages accédés par point pertinent pour une taille de la base 64x 64 avec
m=2485 points.
On a:
q=taille de la requête par intervalles(q=O si requête exacte)
r=nombre de requêtes
N=taille de la base
m=nombre d'enregistrements
I=nombre de noeuds internes du S+-arbre
L=nombre de feuilles du S+-arbre
q,r
Tri-Hilbert
Tri-z-ordre
1=106,L=1667
1=103,L=1365
0.20
0,480
0,521
1.25
0,478
0,513
2,10
0,468
0,506
3,15
0,471
0,514
24

---

25
fig .32 Nombre de pages accédés par point pertinent pour une taille de la base 256 X 256 avec
m=4853 points.
2.4 Les travaux de Yagadish
Reprenant les deux travaux précédents, Yagadish[1990] mena une étude
détaillée sur l'évaluation des performances des courbes de Hilbert, de Gray,
z-courbe. Les expérimentations concernent essentiellement le clustering
dans un espace 2-dimensionnel quand on a des requêtes par intervalles.
La première expérience s'effectue dans une base de taille 128 x 128.
Les requêtes sont carrées. On fait varier leur taille et on mesure le nombre
de pages séquentiellement accédées. Ce nombre est enfin normalisé par le
nombre total de pages de disque accédées.
0,8
....-
....-
0,6
....-
....-
....-
....-
0,4
....-
....-
....-
- - h i l b e r t
....-
0,2
-
-
- z-ordre
0
5
10
15
20
fig.33 La fraction de pages accédées croît quand la taille des requêtes cran.
La courbe de Hilbert est plus
efficace que celle de Gray qui est
meilleure que la z-courbe. Les performances des trois courbes s'améliorent
quand la taille des requêtes augmente.
On s'intéresse ensuite au nombre de points pertinents par page de taille
30 items quand la taille des requêtes carrées croît.
25

---

26
8
6
- - - -
4
2
---hilbert
-
-
-
z-ordre
O + - - - + - - - t - - - - + - - - - + - - + - - - + - - - - - I
8
16
32
64
128
256
512
fig.34 Le nombre de points pertinents extraits en moyenne par page de taille 30 items croit
quand la taille des requêtes carrées croit dans une base de taille 128 X 128
Toutes
les trois courbes
ont
des
performances
qui
s'améliorent
rapidement quand la taille des fenêtres carrées croît. La courbe de Hilbert
est meilleure que les deux autres qui ont des performances égales.
Les expériences suivantes examinent le cas plus général des requêtes
de forme rectangulaire. Celles-ci sont générées à l'aide d'une distribution
faiblement exponentielle. Pour chaque expérience, la moyenne sur 100
rectangles est calculée. On mène alors quatre séries de calcul.
La première concerne la fraction de page lue séquentiellement quand la
taille de la base varie.
0,9
- - - hilbert
-
-
-
z-ordre
0,85
"
/
\\
/
\\
"-
/
\\
"-
...- ......
"-
/
\\
...- ...-
...-
...... ....
...-
0,8
32
64
128
256
512
1024
2048
fig.35 Fraction de page lue séquentiellement quand la taille de la base varie
Pour les trois courbes, cette fraction demeure à peu près constante c'est-
à-dire est indépendante de la taille de la base. Du point de vue des
performances, on a toujours le triplet dans l'ordre Hilbert, puis Gray et enfin
z-courbe.
26

---

27
La deuxième expérience concerne le nombre de points pertinents par
page accédée.
15
...-
,/
10
...-
...-
......
,/
...-
/
...... ,/
...-
/
/
"
5
32
64
128
256
512
1024
2048
fig.36 Le nombre de points pertinents en moyenne par page de taille 30 demeure à peu prés
constant quand la taille de la base varie.
Encore une fois, les performances varient peu avec la taille de la base
et la courbe de Hilbert est meilleure que les deux autres qui ont des
performances égales.
La troisième expérience mesure le nombre de points pertinents quand la
taille des requêtes rectangulaires varie.
25
---hilbert
-
-
- z-ordre
20
15
, /
, /
, /
, /
10
, /
, /
""
5
...-
0
10
100
1000
fig.37 Le nombre de points pertinents extraits en moyenne croît dans une base de taille 512 x
512 quand la taille des requêtes rectangulaires varie.
Quand la taille des requêtes rectangulaires croit, on a une situation
semblable à celle obtenue pour les requêtes carrées.
Enfin la dernière expérience concerne la mesure de l'écartement linéaire
des régions de recherche rectangulaires c'est-à-dire la plus grande distance
entre deux points de la région. Cette distance est ensuite normalisée par
27

---

28
l'aire de la région. Les courbes ont des performances identiques. Cette
mesure n'est donc pas pertinente d'après Yagadish.
2.5 Conclusions
Trois courbes ont été essentiellement étudiées dans le domaine du
clustering dans les bases de données spatiales. Il s'agit des courbes de
Hilbert, de Gray et la z-courbe. La plupart des calculs ont lieu en deux
dimensions. Les mesures de coût calculées sont le nombre de clusters par
requête, le nombre de pages de disques accédées et le nombre de points
pertinents par page accédée. Les deux dernières dépendent du matériel
utilisé ainsi que de la structure d'accès primaire choisie(S+-arbre) pour
stocker les valeurs des clés après le hachage multiclé. On peut se poser
des questions sur l'influence de la forme
des requêtes(carrées ou
rectangles) ainsi que la nature de la distribution choisie pour générer les
requêtes. Pour toutes ces mesures, la courbe de Hilbert est donnée comme
la plus performante.
28

---

Chapitre 3 GENERATEURS DE COURBES DE
PEANO-HILBERT
3.1 NOTATIONS ET DEFINITIONS
Soit n un entier fini positif, et pour chaque i, 1 ::; i ::; n, un entier fini bj ~ 2, et
l'ensemble Bi=[0 .. bj-1]. On note
C=B1 x B2 x
x Bi x
x Bn et c=1 CI =b1
bj
bn.
Et plus généralement, pour tout entier fini m ~ 1, on pose
Bn,m=(B 1)m x
x (Bi)m x
x (Bn)m. De sorte que
C=Bn,1'
3.1.1 Ordre lexicographique:
A chaque élément X=(x1 ,...... ,Xj, ..... ,xn) d'un produit cartésien
C=B1 x ....... xBj x ....... xB n, on associe son rang
n
r(X)= LXi. bi + J. bi + 2..... bn.
i=\\
Cette correspondance
r: C---->[0 ...C-1] est bijective, et induit un ordre total
sur C.
On dira que X ::; X' en ordre lexicographique (OL, en abrégé) si et seulement si
r(X) ::; r(X').
On définit le suivant X' de X comme élément de C, s'il existe, tel que
r(X')=r(X)+ 1.
Si X'=(X'1 ,...... ,x'i-1 ,x'i ...... 'x'n) est le suivant de X en OL, c'est qu'il existe un
indice i, 1 ::; i::; n, tel que
X'tXj, pour 1 ::; j ::; i-1, X'j = 1+Xj' et Xj = bj_1 et X'j =0
pour i< j ::;n.
Si X' est le suivant de x, on dit que X est le précédent de x'. On note alors
X'=suiv(X), et
X=suiv- 1(X'). On dit également que X et X' sont voisins en OL.
Le premier élément de C en OL est
t(C)=(O, ........ ,O), et son dernier élément
3.1.2.0rdre de Gray:

---

30
On appelle ordre ou parcours de Gray (OG, en abrégé) sur
C=B1 x
x Bi x
x Bn, toute application bijective f de [0 c-1] dans
C, telle que pour tout entier r, 0 $; r < c-1, si
x=f(r)
et x'=f(r+1),
alors X et Xl
ne diffèrent que par une seule coordonnée et d'une seule unité. Autrement dit, il
existe un indice i=i[r], et un entier e=e[r]=±1 tels que x'i=Xj + e, et que x'tXj,
si j '" i. On dit que i[r] et e[r] sont les caractéristiques de r ou de x[r].
Si, pour chaque i, on pose si=x1 +
+xi-1, et dj=+1 ou -1 suivant que si
est pair ou impair, (avec d1 =0), la procédure ci-dessous écrite en Pascal
permet
de passer de (X,d) à (X' ,d'):
procedure suivant-gray(var x,d:array[1 ..n] of integer;var im,em:interger);
var i:integer;
begin
i:=n;
while((i<O) and not ((x[i]+d[i]) in [O.. b[i]-1])) do begin d[i]:=-d[i];i:=i-1;end;
im:=i;
if(im>O) then begin em:=d[im]; x[im]:=x[im] + em;end
else write('pas de suivant');
end;
Elle fournit le moyen de parcourir C en ordre de Gray,et de calculer les i[r] et
e[r]:
initialement:
for i:=1 to n do begin x[i]:=O; d[i]:=1;end;
puis:
for r:=O to b1,b2, .......bn-2 do
begin
aHicher(x,r);suivanl-Gray(x,d,i[r],e[r]);
end;
30

---

31
afficher(x);
3.1.3.0rdre de Peano-Hilbert:
Dans
Bn,m'
on appelle ordre ou parcours de Peano-Hilbert(OPH) toute
application bijective Pn,m de [O ...cm-1j dans
Bn,m' telle que pour tout r,
o~ r ~ cm-2. les points x=Pn,m(r) et x'=Pn,m(r+1) ne diffèrent que par une seule
coordonnée et d'une seule unité.
PI
. . .
t ' X-(
.
)
B m
B·m
B m
us preclsemen ,SI
-
x1 ,
,x"
,xn
E
1
x
x
1
X
x
n
•
avec Xj=(xi1 ,,,,,Xij,-,,,xim) E Bi m pour i=1 ,...... ,m,
on veut qu'il existe un entier
i=i[r], tel que Xl ne diffère de X que par la composante de rang i=i[r], et que X'i[r]
soit le suivant ou le précédent de Xi[rj
en ordre lexicographique dans Bnm , et
donc que rang(x'i[rj)=rang(xi[rj) ±1. dans cet ensemble parcouru en OL.
Nous allons voir qu'il est possible de construire un ordre de Peano-Hilbert, en
procédant par récurrence sur m. En effet. pour m=1, on voit que tout parcours de
Gray de C=B ,1 est un parcours en ordre de Peano-Hilbert. Il reste
n
à trouver un
moyen de passer de Bn,m à Bn,m+1' C'est ce à quoi nous allons nous employer.
Nous aurons besoin de définir plusieurs sortes de transformations, ainsi qu'un
nouveau type de produit cartésien.
3.2 Transformations qui conservent l'ordre de Gray ou la
forme de Gray:
Soit un ordre de Gray sur C=Bn,1' Elle induit un ordre total sur cet ensemble.
défini par la suite (f(O),f(1), ..... ,f(c-1)). On dit qu'une application
8 de C dans C
conserve l'ordre de Gray, si la suite
( 8(f(O)), 8(f(1)), ..... ,8(f(c-1)) est un parcours de Gray de C. Autrement dit, il
faut que
8
soit bijective, et que pour r=O,1, ......•c-2. 8(f(r)) et
8(f(r+1)) ne
diffèrent par une seule coordonnée et d'une seule unité.
Nous allons voir deux types de transformations qui conservent l'ordre de Gray:
3.2.1 Transpositions, permutations:
Quels que soient les indices i, j de
1=[1 .. n], i:;t:j, l'application Tij de
31

---

dans
lui-même.
définie
par
Tij(x)=Tij(x1 ,
,xi,
,Xj
,xn)=(x1, ,Xj,
Xj •...• xn) conserve en effet l'ordre de
Gray, si bi=bj, et donc Bj=Bj' De même, la composition de deux ou plusieurs
transpositions, et donc toute permutation des indices de x1, ..... ,xn conserve cet
ordre, dans la mesure où les bj, bj impliqués sont bien égaux.
3.2.2 Complémentations:
Pour chaque indice i de 1. l'application Ci de Bi dans lui-même définie par
Ci(x)=bi-1-x, est telle que si
X'=X + e, alors Cj(X')=Ci(X)-e, avec e=±1.
Prolongeons la à C en posant pour chaque X=(x1, ... ,xi, ....xn) de C,
Ci(X)=(X1, .... ,Ci(Xj), ..... ,X n). Il est aisé de voir que pour chaque i, Ci conserve
l'ordre de Gray.
3.2.3 Forme de Gray:
On dit qu'une transformation
e conserve la forme de Gray si elle conserve
l'ordre de Gray et si, de plus. elle conserve le nombre de composantes par
lesquelles f(O) et f(c-1) diffèrent.
Notons d(x,y) le nombre de composantes par lesquelles x et y diffèrent dans C.
Alors 8 conserve la forme de Gray si elle conserve l'OG
et
d(8 (f(O)), 8 (f(c-1 )))=d(f(O), f(c-1 )).
3.3. Transformations qui conservent l'ordre ou la forme de
Peano-Hilbert:
Généralisons les transformations précédentes, pour m > 1.
Comme ci-dessus, on dit qu'une application 8
de Bn,m dans lui-même
conserve l'ordre de Peano-Hilbert si la suite
(8(Pn,m(O)), 8(Pn,m(1)), .. , 8(Pn,m(cm.1))) est un parcours de Peano-Hilbert de
Bnm' Autrement dit, il faut que 8 soit bijective, et que pour r=0,1 ,....cm-2,
8(Pn,m(r)) et 8(Pn,m(r+1)) ne diffèrent que d'une seule coordonnée et d'une seule.
au sens de Peano-Hilbert.
On dit qu'une transformation 8 conserve la forme de Peano-Hilbert si elle
conserve l'ordre de Peano-Hilbert et si, de plus, elle conserve le nombre de
32

---

33
composantes par lesquelles Pn,m(O) et Pn,m(cm-1) diffèrent. Avec les notations ci-
dessus, on doit donc avoir
3.3.1 Transpositions, permutations:
L'application Tj,j de B1 m x
xBjm x
xBjm x
xBnm dans
B1 m x ........ xBjm x ......... xBim x ..... xBnm
qui transforme
conserve
évidemment l'ordre de Peano-Hilbert. Et donc, toute permutation des indices de
variables x1 ,....... ,xn en fait autant. Mais ce n'est que si bj=bj, et donc Bi=Bj, que
Ti,j est une transformation de Bn,m. C'est pourquoi nous serons contraints
ultérieurement à n'examiner que le cas où tous les bj sont égaux, pour nous limiter
aux seules transformations de Bn.m.
3.3.2
Complémentations:
Pour chaque indice i de l, soit Ki:Bn m----->Bnm ' l'application définie pour tout
.
,
Kj(xj)=(Ci(xi1), .... ,Cj(xij), ....... ,Ci(Xim»
E
Bi m .
Soit Xl le suivant de X en OPH dans Bnm' Donc X et Xl ne diffèrent que par
une seule coordonnée d'indice i=i[r]
et x'i est le suivant ou le précédent de xi en
CL.
Par hypothèse, on a Y'j=Yi+e,
avec e=±1,
m
m
Yi= L Xij (bj)m-j ,
Y'j = L X'ij (bj)m-j
j~1
j~l
33

---

17
Il
On voit que zi= L Ci(Xij)(bi)m-j
= L (bj-1-xij )(bi)m-j
J=I
j=1
Z'i=Zi +e avec e=±1. Ainsi Ki(xi) et Ki(x'i) sont voisins en Ol dans Bi m , et donc
Ki(X) et Ki(x')
sont voisins dans
OPH
dans Bn,m
--Pour i:;:. i[r] , on a
x'i=xi
' et donc
Y'j=Yi
et
Z'j=zi. Comme X'i[r]
est
voisin de
Xi[r] en Ol dans
Bi m , on voit que
Ki(X) et Kj(X')
sont voisins
en OPH dans Bn,m'
De plus, l'opération Ci étant involutive, car X = bi -1 - Ci(X), il est facile de voir
que les Kj sont bijectives. Ce qui prouve qu'elles conservent bien l'ordre de
Peano-Hilbert.
3.3.3 Remarques:
1) D'un point de vue géométrique, on peut considérer dans l'espace [O ... b1 m.1]
x
x[O
b m
n -1]
des
(Y1,
'Yn) ,qu'une transposition
T"
est une
l ,j
symétrie par rapport au plan d'équation
Yi = Yj , et qu'une complémentation Kj est
une symétrie par rapport au plan d'équation
Yi = (b1 m-1)/2.
On
notera que les transpositions, et donc les permutations, laissent l'origine
invariante, et que les complémentations la déplace.
Enfin, pour tout
u=(u1 ,....... ,Uj, ..... ,u n) de
{a ,b1-1
} x ..... x {a ,bi-1
} x ..... x {a ,bn-1
},
nous définissions une
complémentation généralisée
comme l'application
Ku : Bn m------->Bn m
,
,
qui est la composée des Kj
pour les
tels que
ui = bj"1.
2)
En désignant, pour tout i, par B'i= {a ,bj"1
} le sous-ensemble de Bi, et
par
B'n m =B'1 m x .... x B'n m, on constate que l'image de tout élément de B'n m par
,
,
transposition
ou
par
complémentation,
et
donc
par
permutation
ou
complémentation généralisée, est encore un élément de B'n,m . De plus, si deux
éléments v et w de B'n,m diffèrent par k coordonnées, leurs images v' et w' par
34

---

35
toute permutation ou complémentation généralisée, différeront encore par k
coordonnées.
3) Par conséquent, que m = 1. ou m > 1, les transformations généralisées par
permutation ou complémentation ont la même signification géométrique. elles
conservent l'OPH, et les distances entre points de S'n,m (au sens que les images
de deux points diffèrent par le même nombre de coordonnées que ces points).
C'est pourquoi, sauf exception, on ne précisera pas la valeur de m.
3.3.4 Produit cartésien "collé".
Soient k, 1 deux entiers finis positifs. Supposons disposer d'un parcours en
OPH pour chacun des ensembles
Sn,k et
Sn,!"
Nous allons essayer d'en
construire un pour Sn,k+/'
A tout X=(X1,
Xj , ,xn) de Sn,k' avec Xi=(Xi1 ,
,Xik)
E Sik, pour i=1,
,n.
et à tout Y=(Y1, ·.,Yi ,.. ·,Yn ) de Sn,l' avec Yi =(Yi1 ,..·.... ,Yil) E Sil , pour i= 1,
n,
associons l'élément
Z=(Z1 ,
,Zi ,
,zn) de Sn,k+1 tel que
Zi = (Xi, Yi) =(Xi1 ,
,Xik .Yi1 ,.·
,Yil)
E
sri, pour i= 1
n.
Nous poserons
Z = X • y. On voit que
Z est obtenu par collement ou
concaténation des coordonnées de mêmes indices que X et y.
Nous poserons également
X· Sn k = U
U
X'y
, et
Sn,k • Sn,1
=
x·Bn.1
,
y ESn.!
yESn.!
1) Il est aisé de voir que l'application de
Sn,k x Sn,1
dans
Sn,k+1
définie par
(X,y)------>Z=X • y, est bien une bijection, car pour tout
X, si
y;t: yi
. on a
X·y = X·y' ,et si
X oF- X', alors X·y = X'·y.
Il s'ensuit que pour tout X, l'ensemble X· Sn,1 est de même cardinalité que
Sn,1 ,que X ·Sn,1
et X' "Sn,1 sont disjoints si
X;t: X', et que Sn,k· Sn,1
et
Sn,k+1 peuvent être mis en bijection par cette opération •.
Et nous dirons que
Sn,k • Sn,1
est le produit collé de
Sn,k et
Sn,l.
35

---

36
2) Si Bn,1
est muni d'un OPH, soit
(t(Bn,l) ,
,y,y', .. " .. ,q(Bn,I))
la suite
des éléments de
Bn,1
écrite dans cet ordre de Peano-Hilbert, y et yi désignant
deux éléments consécutifs. On voit sans difficulté que
(X * t(Bn,\\),,,.,X*Y,X*Y',,,,,,X* q(Bn,I)) détermine un OPH sur
X *Bn,1 . Et plus
généralement, si 8
est une transformation qui conserve l'OPH de
Bn,l, alors
(8 (t( Bn,1 )),,,.,8(y),8(y'),,,,,,8(q( Bn,1 ))) constitue un OPH pour 8 (Bn,l) et
(X * 8 (t( Bn,1 )),,,.,X * 8(y), X * 8(y'),,,,,, X * 8(q( Bn,1 )))
est
un OPH pour
X * 8 (Bn.!)
.
3) On peut définir un ordre total sur
Bn,k * Bn,1 , et donc sur
Bn,k+1 ,en posant
z=x*y :::; X' * yi, si et seulement si, X < Xl
dans l'OPH de Bn,k, ou X=X', et y:::;y'
dans l'OPH de
Bn,l' Ce qui revient à dire que dans cet ordre tout élément de X *
Bn,1
précède tout élément de X' * Bn,l, si X précède X' dans Bn,k ,et que si
X =
X' , x· Y précède
X· yi , si y précède yi dans Bn,l' Plus généralement, si pour
tout X de Bn,l' 8 x est une transformation de Bn,1 qui conserve l'ordre de Peano-
Hilbert, on peut définir un ordre total sur Bn,k * Bn.! ' en posant Z=X*y :::; X'* yi si et
I
seulement si, X < X' dans Bn,k ,ou si X=X , et
8 x M :::; 8 x (yI) dans Bn,l.
Nous exprimerons cet ordre total, en écrivant que
q(Bn,k)
Bn,k+l=
L:X*8x(Bn,')
x=I(Bn.k)
Sachant que l'OPH sur
Bn,k est décrit par la suite
(t(Bn,k) ,,,,,.,,.,,.,X,X',,,,,,,,q(Bn,iJ), cette égalité signifie qu'on parcourt
X· 8 x (Bn,l) , successivement pour X=t(Bn,iJ ,,,,,,,,,,X=q(Bn,iJ .
3.3.5 Conditions de raccordement (ou de continuité) :
Nous venons de voir que si
Bn,k et
Bn.! sont tous deux munis d'un OPH, on
peut définir un grand nombre d'ordres totaux sur
Bn,k+1
,en choisissant pour
36

---

37
chaque X de
Bn.k une transformation qui conserve l'OPH de Bn.k. Si Xl est le
suivant de X dans l'OPH de
Bn,k, on voit qu'on parcourt la suite
( X " 8x(t( Bn 1», ... ,X * 8x(Y), X * 8x(y'), .... , X * 8x(q( Bn 1))) , puis la suite
,
,
I
( X * 8x,(t( Bn1», ... ,X' * 8x'(Y)' Xl * 8x·(y'), .... , Xl * 8x,(q( Bn1))).
,
.
Ce qui fait que le suivant de l'élément
X * 8x(q( Bn1» est Xl * 8
.
x·(q( Bn1
, ».
Si on veut que cet ordre total soit un OPH sur Bn,k+l, il faut que pour tout X.
sauf q(Bn,k) , ces deux éléments ne diffèrent que par une seule coordonnée et
d'une seule unité au sens de Peano-Hilbert. Posons provisoirement
8x(t(Bn,,»=t=(t, ,.. ,ti, .. ,tn) E Bn,l, avec ti=(ti1 ,
,tij,
,til) E
Bi,l, pour i=1 ,
n,
8x(q(Bn,I»=q=(q, ,··,qj,.. ,qn) E Bn,l. avec qj=(qi' , ,qij•.... ,qil) E Bi, pour i=1 •.... n,
8x,(t(Bn,I»=t'=(t', ,.. ,t'i, ... ,t'n) E Bn,l, avec t'i=(t'i' , ,t'ij•.. ,t'il) E Bil • pour i=1 ,... ,n,
X=(x, ,...... ,Xi, .... ,Xn) E Bn,k, avec Xi=(Xi' ,......,Xij, .... ,xiiJ E Bik , pour i=1 ,....n,
XI ( ,
,
•
)
B
' (
,
,. \\
= x" .... xl, ..... x n E
n.k, avec Xi= X·i' .... ,Xij, .... ,XiKJ E
Bik , pour i=1 ,... ,n.
On a donc X * 8x(q(Bn 1» =X*q= ((x, ,q,),
(Xj,qi), .... ,(xn.qn»,
Xl * 8x.(t(Bn 1» =X'"t'= ((x', ,t',), .... (x'j,t'j),
,(x'n't'n»
Or X parcourt
Bn,k
en OPH. Il existe donc un indice
i=i(x)=i[r]. si r
est le
rang de X dans
Bn.k parcouru en OPH, tel que pour tout i;ti[r] , on ait X'j=Xj,
et que pour
i=i[r], X'i
soit le suivant ou le précédent de
xi en Ol dans Br
Explicitement, il existe un indice j de [1 .. k]
tel que pour tout
j'< j, on a: X'ii' = Xij'
et
-- X'ij=Xij+1, et Xij' =bj -1 , et x'ij' =0. pour j' > j, si Xl est le suivant en Ol de X.
-- X'ij =xir1. et Xii' =0,
et x'ij' =bj -1 , pour j' > j, si Xl est le précédent en Ol
de X
Examinons le premier cas. Si on veut que X' * t'
soit le suivant en OPH de
X"q,
il faut que
X' * t' ne diffère de X * q
que par une seule coordonnée et
d'une seule unité. Comme xi = x'i pour tout i;ti[r] , on voit que
X *q
et
Xl * t'
ne peuvent différer que par la coordonnée d'indice
i[r], et que:
a) pour tout Î;ti(r] , on doit avoir
qi = t'i ;
37

---

38
b) pour
i=i[r], (X'i,t'i)
doit être voisin de
(Xj,qj)
en OL dans
Bn,k+l. Du fait
que X'j est le suivant de Xj en OL dans Bn,k, cela ne peut se faire que si
qi=(b,-1 ,... ,bj-1), et t'i=(O, ..... ,O) E Bn,l'
Pour les mêmes raisons, dans le second cas. on devrait avoir
a)
qj= t'j
pour tout
j,.:i[r], et
b) t'j=(bj-1 .... ,bj-1), et qj= (0, ..... ,0)
E
Bn,l. en i=i[r]
3.3.6 Construction récursive d'un OPH sur
Bn.m:
Supposons avoir déterminé pour r = O, ....... ,c- 1, une transformation
8r de
Bn,1' ou, ce qui est équivalent comme nous l'avons vu, de
Bn,m, qui conserve la
forme de Peano-Hilbert.
Notons
Gn=(f(0), ... ,f(r), ,f(c-1)), la suite des éléments de
C=Bn 1 en ordre
de Gray, et Pn,m = (9nm(0),
,9nm(cm·1))
la suite des éléments de
Bn.m en
OPH.
Le procédé ci-dessous permet de construire récursivement Pn,m, pour m=1,2.
Procédure Peano-Hilbert (n,m : entiers) ;
début
G=Gn ;
si (m=1) alors P:=G
sinon
début
O:=P(n,m-1); L:="; {liste vide}
pour r:=à à c-1 faire L:= L+ f(r)' orla);
{où '+' exprime la concaténation de listes}
P:=L;
fin
fin.
38

---

39
Il consiste à partir de Pn,1= Gn ,qui est l'ordre de Gray sur
Bn,1 =C, puis à
déterminer ensuite l'OPH
sur
Bn,m = Bn,1 * Bn,m-1 = C * Bn,m-1
On voit ainsi qu'il suffit de déterminer pour chaque r de
[0 ... c-1] une
transformation
8 r qui conserve la forme de Peano-Hilbert.
Nous allons nous employer à déterminer de telles transformations, en nous
limitant au cas où tous les bj sont égaux au même entier fini b>1, et Bj=B=[O .. b- 1],
pour que ces transformations se fassent dans les Bn,m , comme nous l'avons déjà
souligné. Si b est pair, on dira qu'il s'agit d'ordres ou courbes de Hilbert, et
sinon d'ordres ou de courbes de Peano.
En fait, nous verrons que la détermination de ces transformations peut se faire
via la résolution d'un système d'équations vectorielles.
Notons, pour chaque ensemble fini totalement ordonné E, t(E) et
q(E)
ses
premier et dernier éléments. Posons
Om=(O,
,O) et (b-1 )m=(b-1 ,
,b-1) pour
tout m > O.
Commençons par calculer les éléments extrêmes de
Gn. et de chacun des
Pn,m·
Il est aisé de voir que quel que soit la parité de b, on a
t(Gn)=(O ......O)
E
Bn=c.
Par contre si b est pair, on a
q(G n)=(b-1 ,0, .... ,0) ,
et si b est impair,
q(Gn)=(b-1, .... ,b-1) E Bn=C.
Dans la suite des éléments de Gn, qui sont les éléments de
Bn,1 =Bn =C,
parcourus en ordre de Gray, nous noterons, pour chaque r ,0~r~c-1, x[r] l'élément
de rang r, 8 r la transformation associée à
x[r]. De sorte que le suivant
Xl de
X sera
x[r+ 1] . Et si t(Bn,l) et q(Bn,l) sont le premier et le dernier éléments de
Bn,1 , parcouru en OPH, nous poserons:
t[r] =8 x((t(Bn.1 )) = 8 r((t(Bn,1 )) = (t[r,1 ],
,t[r,i],
,t[r,n]) E
Bn.1 ,
q[r] =8 x((q(Bn,1 )) = 8 r((t(Bn.1 )) = (q[r,1 ],
,q[r,i],
,q[r,n]) E
Bn,1
On sait
que pour passer de
X=x[r]
à Xl = x[r+1] • il faut modifier la
coordonnée
i1 [r] de x[r]
d'une quantité égale à
e[r] =±1
et que,
39

---

-w
si i= i1 [r] ,alors
-si e[r]=+1, on doit avoir q[r,i]=(b-1 ,.. ,b-1)=(b-1)1 E Bn.1 et t[r+1 ,i]=(O)1 E Bn,l,
-si e[r]=-1, on doit avoir q[r,i]=(O)i E Bn,l, et
t[r+1, i]=(b-1)1
E
Bn,1
et que pour tout
i", i1 [r] ,on doit avoir t[r+1, i]= q[r, i]
Choisissons les transformations
8 0 et 8 C-1 telles que
8 0 (t(Bn,I»= t(Bn,I), et 8 C-1(q(Bn,I»= q(Bn,I),
que nous appellerons conditions aux extrémités, et qui expriment que l'on
souhaite que les points extrêmes de
Bn,I+1
ressemblent à ceux de
Bn,l.
D'après la construction de
Bn.I+1 à partir de Bn,l, on voit qu'on a alors:
t(Bn,1+1 )=t(G n) * 8 0 (t(Bn 1
, »= t(G n) * t(B n 1),
,
q(Bn,1+1 )=q(G n) * 8 C-1 (q(Bn 1»=
,
q(Gn) *q(Bn 1)'
,
On en déduit, en raisonnant par récurrence sur l, que
-si b est pair ,alors q(Bn.m) = ((b_1)m,om, ...... ,om) E Bn,m
-si b est impair ,alors q(Bn,m) = ((b-1)m,(b-1)m, ...... ,(b-1)m)=((b-1)m)n
E
Bn,m
pour tout n, et tout m
On remarque alors que:
a) quelque soit m, on a
d(t(Bn,m),q(Bn,m»=d(t(Bn,1),q(Bn.1» = n si b est impair, et = 1 si b est pair.
Il s'ensuit que si les
8 r
conservent la forme Peano-Hilbert, on doit avoir pour
tout r,
d(8r(t(Bn,m»,8r(q(Bn,m)))=d(t(Bn,m),q(Bn,m) = n si b est impair, et
1 sinon.
Autrement dit, si b est impair
8 r(t(Bn,m»
et 8 r(q(Bn,m» doivent différer par
toutes leurs coordonnées, et si
b est pair 8 r(t(Bn,m» et 8 r(q(Bn,m» ne doivent
différer que par une seule coordonnée.
b) soit
B'={O,b-1}. On voit que pour tout
n, et tout
m, on a
t(Bn,m)
et
q(Bn,m) E B'n.m de sorte que si on se limite à des transformations 8 r composées
de permutations d'indices de coordonnées, et de complémentations dans
B ou
Bn,m, les transformées de
t(Bn,m) et q(Bn,m)
par ces
8 r
continueront à
-w

---

~ 1
appartenir à S'n,m
et que, de plus, ces transformations conservent bien la forme
de Peano-Hilbert, car non seulement elles conservent l'ordre, mais également
C'est pourquoi, nous n'envisagerons pas de recourir à d'autres transformations
que celles qui sont composées de permutations et complémentations.
Les remarques précédentes permettent donc de limiter le domaine des valeurs
que peuvent prendre les
tIr]
et
q[r]
à l'ensemble
S'n,m
et celui des
transformations 8r qui conservent la forme de Peano-Hilbert à l'ensemble
e
des composées de permutations et complémentations dans la base
b.
On est ainsi amené à déterminer pour r=0, ....... ,c-1, un couple
(t[r],q[r])
d'éléments de Sn,m, tels que
-t[O] = t(Sn,I)=(OI,OI, ....... ,OI)=(ol)n ,
-d(t[r] ,q[r] )= n
si b est impair, et = 1 si b est pair;
-d(q[r] ,t[r+1])= 1 , avec
- -pour i= i1 [rI ,
- - -si
e[r] =+1 , q[r, i]=(b-1 ,.... ,b-1)
Sn l,
,
et t[r+ 1, i] = (01)
E Sn ,l ,
- - -si
e[r] =-1 , q[r, i]= (0)1
E
Sn,l, et t[r+1, i] = (b-1)1
E Sn,1
- -pour i:;t: i1[r], t[r+1, i] =q[r, il;
--q[c-1] =q(Sn,I)=«b-1)1, 01,
, 01) E Sn,1 si b est pair, et
q[c-1] =q(Sn,I)=«b-1)1, (b-1)1
(b-1)1) E Sn,1 =«b-1)I)n
si b est impair.
Du fait que l'on connaît t[O], et q[c-1], et que t[r+1] se déduit immédiatement
de q[r], quand on connaît les i1 [rI et e[r], le calcul des tIr] et q[r]
peut se faire
séquentiellement par la boucle:
pour r:=O à c-2
calculer q[r] puis t[r+1], connaissant tIr] , i1 [r] et e[r].
3.3.7 Détermination des t[r],q[r]pour n quelconque >1, et 1= 1.
On suppose avoir calculé une fois pour toute les
i1 [r]
et
e[r]
par
l'algorithme de Gray.
1) courbe de Peano, b impair:

---

-1-2
pour tout X=(x" ..... ,Xj, ..... ,xn) C'=8'n, notons K(X)=(C1(X'), ... ,C1(Xj), .... ,C1(xn»,
avec C,(xj)=b-1-xj, pour i= 1, ... ,n.
On voit que X et
K(X)
diffèrent par toutes leurs coordonnées.
La détermination des t[r], C1[r], peut se faire comme suit:
t[O]:=(O,......,O)
E
B'n;
pour
r:=O
à
c-1
faire
début
q[r]:=K(t[r]); t[r+1]:=q[r];
si (e[r] > 0) alors t[r+1, i1[r]]:=0;et sinon t[r+1, i1[r]]:=b-1;
fin;
Il n'y a qu'une solution et une seule. C'est dû au fait que pour tout r, q[r]
est
entièrement déterminé par t[r],
puisqu'il diffère de t[r]
par
toutes ses
coordonnées. Le fait que
q[r, i1 [rJ] = b-1
ou 0, suivant que e[r] = +1
ou -1 ,
n'influe en rien sur
q[r]. Il
intervient par contre dans le calcul de
t[r+1]. On
s'assure enfin que
d(t[c-1], q[c-1J] = n
car q[c-1]
est donné et vaut (b-1)n.
2) Courbes de Hilbert, b pair:
la détermination des
t[r], q[r], est ici plus délicate, car
q[r]
ne diffère de
que par une seule coordonnée dont nous appellerons
i2[r]
l'indice. Pour chaque
r, on est donc amené à envisager toutes les possibilités, suivant que
i2[r] =1,2, .... ,n. Cela peut se faire au moyen d'une procédure exploratoire
arborescente, qui évite d'examiner toutes les
nC possibilités pour
( i2[0] ,i2[1]
;....... ,i2[c-1]).
C'est la démarche que nous avons suivie. Elle
fournit en particulier pour
b=2, un seul ordre quand n=2,
5 ordres différents
quand
n=3, et 5733 ordres différents quand n = 4.
3.3.8 Détermination des transformations conservant la forme de Peano-
Hilbert pour 1= 1 :
-1-2

---

-+3
De la connaissance des couples t[r], q[r], Og~c-1 , nous allons déduire les
transformations
8 r. Il suffit en effet, pour chaque
r , de trouver une
transformation 8=8r E 8, telle que
8 (t(Bn l))=t[r], et 8 (q(Bn l))=q[r].
Soit la transformation
8 t[rl' Elle transforme t(Bn,l )=(o)n
en
t[r], et q(Bn,l)
en un élément q'[r] de Bn,l'
- Si q'[r] = q[r] , on prend 8 r =8.
- Sinon, on sait que
d(t[r], q'[r]) =d(t(Bn,ü, q(Bn,l)) = n ou 1 suivant que b est
impair ou pair.
- - Dans le cas où b est pair, c'est que
q'[rj
est constitué de
n-1
chiffres
'0' et d'un chiffre 'b-1 '. Désignons par
i l'indice de la position telle que q'[r, i]=1.
La transposition d'indices T1,i
amène ce "0" en position 1, donc transforme
q'[r] en (1,O, ... ,0)=q(Bn,1), sans transformer t(Bn,l)'
On a donc q'[r] =Kt[r] (q[r]) , q(Bn,ü= T1,i(q'[r]) .
Du fait que ces deux transformations sont involutives, on a :
q[rj=Kt[rj (q'[r]) =Kt[rj.Tl,j(q(Bn,l)), et de même t[r]= Kt[r].T1,i(t(Bn,l))'
Ce qui fait qu'on peut prendre
8r=Kt[r]. Tl ,i.
- - pour b impair, on sait que d(t(Bn,ü,q(Bn,l))=n. La transformation 8= Kt[r]
transforme t(Bn,l) en t[r], et q(Bn,l)en un élément qui diffère de t[r]
par toutes
ses coordonnées, c'est à dire en
q[r].
Ainsi,
- pour b impair, il suffit de prendre
8 r=Kt[r],
- pour b pair,
- - si la transformée de q[r] par Kt[r] est égale à (1,0,. ,0), alors on prend
8r= Kt[r].
- - sinon, on prend
8r=Kt[r]. Tl ,i si
est l'indice de la composante de la
transformée qui vaut 1.
3.3.9 Détermination des transformations qui conservent la forme de
Peano-Hilbert pour 1>1
-+3

---

Nous allons montrer que les transformations
Br que nous avons obtenues
pour 1= 1, peuvent également convenir pour 1> 1, si on les considère en tant que
transformations généralisées, comme nous l'avons vu plus haut.
En effet, les
Gr
initiales, (c'est-à-dire celles relatives à 1=1). sont des
composées de complémentations et de transpositions portant sur
B'n,I=B'n. Les
Br généralisées à
Sn,l, 1> 1, sont donc, d'après ce que nous avons vu plus haut.
des transformations qui conservent la forme de Peano-Hilbert. Il nous reste donc à
montrer qu'elles satisfont les contraintes de raccordement.
Nous avons vu que pour 1=1, et pour r = 0, ..... c - 2, quand r augmente de 1.
on passe de x[r] à x[r+'I] en augmentant sa coordonnée d'indice i1 [r] de e[r]=±1,
et que Br
fait passer de
Br (q( Bn,1»
à Br +1 (t( Bn,1»
en changeant sa
coordonnée d'indice
i1 [r]
de b-1 en 0 si
e[r] = +1
et de 0 en b· 1 sinon.
Or, pour
1 > 1, la transformation
Br
généralisée fait passer de Br (q( Bn,l»
à Br +1(t( Bn,l» en changeant sa coordonnée d'indice
i1[r]
de (b-1)1
en
(0)1
si e[r]=+1, et de (0)'
en (b-1)1
sinon. Ce qui fait que dans chacun des deux
cas,
x[r+ 1] • Br +1 (t(Sn,'»
est le suivant en OPH de
x[r]· Br(q(Bn,l»
dans
Bn,I+1' Et qui montre que les conditions de raccordement sont bien remplies par
les
Br
généralisées.
3.3.10 Conclusion:
Nous
venons de
voir que
les courbes de
Peano-Hilbert
peuvent
être
entièrement déterminées et construites à partir de courbes de Gray. On peut dire
que les courbes de Gray constituent, en quelque sorte, le "patrimoine génétique"
des courbes de Peano-Hilbert, dans la mesure où, pour la précision
m = 1 • ces
courbes ne sont que des courbes de Gray, et que pour m > 1, toute courbe de
Peano-Hilbert est
constituée de
c=bn copies de la courbe de précision
m - 1.
chacune des copies ayant subi une transformation géométrique simple, elle même
donnée par la courbe de Gray, pour être raccordée à ses voisines.

---

Chapitre 4
CLUSTERING EN DIMENSION 2
4.1 PRELIMINAIRES
4.1.1 Position du problème
Soit une base de données de taille b2m en supposant que b=2, que la
dimension n de l'espace est égale à 2, que les points sont stockés selon l'ordre de
Hilbert. Soit
F une fenêtre [ua,val • [u1,v1l représentant un objet spatial à
rechercher où une requête par intervalles. Le problème consiste à rechercher les
c1usters qui sont dans la fenêtre F et à calculer leur nombre. Quand la taille de la
base n'est pas très importante, ce calcul est rapide. Mais si celle-là devient
élevée, le calcul devient très long. Il s'avère alors indispensable de trouver un
algorithme efficace. Il s'agit par exemple de trouver un moyen de ne pas examiner
les points qui sont en dehors de la fenêtre F.
. 4.1.2 Algorithme
On divise d'abord la base en b2 =4 parties correspondant à la décomposition
de Hilbert d'ordre 1. On numérote ces quatre parties selon leur rang dans l'ordre
de Hilbert et on les enchaîne dans une liste. On obtient alors une liste ordonnée
d'hypercubes(carrés) H. Alors on compare successivement chaque élément de la
liste à la fenêtre F. Soit
H élément courant de la liste.
Si intersection(F,H) = intersection de F et de H est vide alors on passe à
l'élément suivant de la liste après avoir donné à H un statut égal à O.
Sinon si H est entièrement contenu dans F alors on donne à H un statut
égal à 1 et on passe à l'élément suivant.
Sinon
on décompose
H en quatre parties correspondant en
une division de Hilbert d'ordre 2. On numérote ces quatre sous-parties selon le
balayage
de Hilbert correspondant au même ordre d'approximation. On a ainsi
une chaîne de quatre hypercubes. Alors dans la première liste on remplace
H
par cette sous-chaîne. On obtient donc une liste où l'élément courant
H est le
premier élément de la sous-chaîne qu'on compare de nouveau à la fenêtre F.

---

A la fin du processus, on obtient une liste ordonnée, selon l'ordre de Hilbert,
d'hypercubes qui ont un statut égal à 0 ou à 1.
Un cluster n'est alors qu'une
succession continue d'hypercubes de statut égal à 1.
Algorithme
H=base entière=[O,1)2, statut(H)=2;
liste2=éclatement(H);
Iiste=liste2;
H=début(liste);
tant non fin(liste) faire
si intersection(H,F) est vide alors {statut(H)=O;suivant(liste);}
sinon si H est contenu dans F alors {statut(H)=1;suivant(liste);}
sinon {
si côté(H)=1 alors suivant(liste)
sinon
liste2=éclatement(H);liste=remplacer(liste,liste2);}
nbcluster=O;
H=dèbut(liste);tant que non fin(liste) faire{
si statut(H)=1
alors
nbcluster=nbclusrer+1;
tant que ( statut(H)=1 et H non fin (liste)
suivant(liste);}
sinon suivant(liste);
46

---

47
On a utilisé les procédures suivantes:
_début(liste) se positionne sur le premier élément de liste.
_fin(liste) se positionne sur l'élément NULL qui suit le dernier élément de la
liste.
_suivant(liste) retourne l'élément suivant.
_remplacer(liste,liste2) remplace dans liste l'élément courant H par Iiste2; la
nouvelle liste obtenue est encore appelée liste et l'élément courant H de cette liste
finale est le premier élément de liste2.
_intersection(H,F) retourne 1 si H est contenue dans F, 0 si l'intersection est
vide et 2 sinon.
_statut(H)=i ntersection (H, F);
_éclatement(H) retourne une liste ordonnée de bn=22 hypercubes provenant
de la subdivision de H.
En effet, H est d'abord divisé en bn hypercubes. Chaque hypercube est
connu par les coordonnées de son sommet minimal et le rang de ce sommet dans
l'ordre de Hilbert correspondant à l'approximation courante.
_côté(H) retourne la valeur du coté de l'hypercube H.
On trouvera en annexe le programme complet en langage C implémentant cet
algorithme.
4.1.3 Conditions de l'expérimentation
4.1.3.1 Choix d'une distribution
Le nombre de clusters dans une fenêtre F dépend d'abord de la position dans
l'espace de F. Or pour une base de taille 210 * 210 par exemple, il y a
(2 1O-c)*(2 1O-c) positions possibles dans le plan pour une fenêtre carrée F de
côté c. Il s'agit alors de choisir une distribution de probabilité pour les positions.
I\\lous avons fait le choix d'une distribution uniforme dans le plan. Grâce à un
générateur de nombres aléatoires, on obtient les fenêtres et leur position tout en
fixant la valeur de leurs cotés.
47

---

4.1.3.2 Dépendance par rapport à la forme
Le nombre de clusters dans une fenêtre F dépend aussi de sa forme.
Celle-ci peut être carrée ou rectangulaire. Et pour une même taille de fenêtre, le
nombre de clusters varie fortement
suivant
que
la forme
de la fenêtre
est
carrée ou rectangle.
4.2 COMPORTEMENT DU NOMBRE DE CLUSTERS EN
FONCTION DE LA TAILLE DE LA BASE, CELLE
DE LA FENETRE ETANT CONSTANTE.
4.2.1 Motivation
Le nombre de clusters obtenu quand la taille de la base varie pour une taille de
fenêtre donnée est le principal
paramètre qui nous intéresse. En effet, c'est le
seul critère qui ne dépend pas du matériel utilisé.
4.2.2 Expérimentations
Ces résultats sont obtenus en faisant la moyenne sur 200 cas. Ce sont des
fenêtres
F =[c1 ' c2] où c1 est la longueur et ~ la largeur. On fait alors la
moyenne des nombres obtenus. Plus la taille de la base est élevée, plus est
grande le nombre de positions possibles des fenêtres. On examine les fenêtres de
la taille 4 jusqu'à la taille 400. Pour chaque, s'il ya lieu, on examine tous les cas
de figures possibles quant à la forme de la fenêtre. Par exemple, pour la
taille 8 * 8, on examinera les fenêtres 2*32 et
4*16.
48

---

49
3
-- - - - - - - - -~----------------
- - - - "
8
7
6
.-....
,," ...... _----- ..
5
---Hilbert
4
-
-
- z-<>rdre
. . . . . . . . - ... _- ......
- - - •• Peano
3
2
3
4
5
6
7
8
9
10
11
12
13
14
15
fig.39
F=(S,2)
49

---

50
9
,
..... --- ...
8
7
6
---Hilbert
...........................................
5
-
-
-z~rdre
• - - - - Peano
4+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--
2
3
4
5
6
7
8
9
10
11
12
13
14
15
figAO F=(5,5)
11
... ... ... ... .. .. ... " .......
.. ............
10
...
9
8
7
6
..............
.. .....
- - - Hilbert
- - - z-ordre
5
... - ........ Peano
4
2
3
4
5
6
7
8
9
10
11
12
13
14
15
figA1
F=(6,6)
50

---

51
17
.' .
............... ~ ....... .. .............
. .
16
. .
.
15
14
13
12
11
10
.. .. .... .. .. ............. . ..
9
- - - Hilbert
8
~
- - - Z-ordre
..........
7
Peano
6
3
4
5
6
7
8
9
10
11
12
13
14
15
fig.42
F=(2,18)
14
- - - - - - - - - -~--------------
13
1
1
........................ ~
12
1
1
11
1
1
10
9
- - - Hilbert
..
-
-
-
Z_ordre
8
.........
- - - - - Peano
7
2
3
4
5
6
7
8
9
10
11
12
13
14
15
fig.43
F=(3,12)
51

---

52
11
....
-
~
~
-
..
10
9
,
,
8
7
1-
.
. -
6
- -
:::..:=-::,.;::::---------------j - - - Hilbert
-
-
-
Z_ordre
5
• • • •.
Peano
4
2
3
4
5
6
7
8
9
10
11
12
13
14
15
fig.44=(4,9)
52

---

53
27
23
19
.. .. ..
..
..
~
- - - Hilbert
15
t- _
_ _
_
_
_
-
-
-
Z_ordre
;::....;=-----------------1
1
- - . . .
Peano
11~·
3
4
5
6
7
8
9
10
11
12
13
14
15
fig,47
F=(2,32)
-_
..
..... -_ ...
... .. .. .. ... .. .
... .. .. ..
15
11
---------=-_--
~--- Hilbert
-
-
-
Z_ordre
- - •• -
Peano
7
3
4
5
6
7
8
9
10
11
12
13
14
15
fig.48
F=(4,16)
53

---

- - - - - - - - - - _=------,,---.:----.":".'Pr"':"."":".-.-.-.-.-.-.-.-.-.-.
17
13
- - - Hilbert
............ -
..
- - •• -
Peano
9
3
4
5
6
7
a
9
10
11
12
13
14
15
figA9 F=(10.10)
...
. ..
...
41
33
25
- - - Hilbert
-
-
-
Z_ordre
- - - - - _::=-:=-==--------------------j
17
~
- - •• -
Peano
4 5 6
7
a
9
10
11
12
13
14
15
fig.50
F=(2,50)
25
.......
.. .. ..
.. ...
- ... -... -.- ...... ~
... ......
- - - Hilbert
17
.
-
-
-
Z_ordre
.
• • • ••
Peano
. . . . . . . . . . . . . . . . -
- - - - - - -
9
4
5
6
7
a
9
10
11
12
13
14
15
fig.51
F=(4.25)
54

---

55
25
........................... -
.
...................
.
20
- - - Hilbert
-
-
-
Z_ordre
15
•••• -
Peano
.......................
10
4
5
6
7
8
9
10
11
12
13
14
15
fig.52
F:(5,20)
20
- - - - - - - - - - ~--"""""'----."""'''''.----.'''''-----,-
:
16
12
- - - Hilbert
...............
-
-
-
Z_ordre
- - •• - Peano
8
3
4
5
6
7
8
9
10
11
12
13
14
15
fig.53 F:(11,11)
23
.. - - ........
- - - - - - - - - .-"'......--;:._....:.......:..._-~~------:;,-.
19
15
- - - Hilbert
-
-
-
Z_ordre
............................
• - - • - Peano
. ..
11
3
4
5
6
7
8
9
10
11
12
13
14
15
fig.54
F:(12,12)
55

---

56
63
.... --_._---------
...
.. .. .. .. ..
53
- - - Hilbert
43
-
-
-
Z_ordre
• • • ••
Peano
33
- - - - ~--=-::..:-=..:-=--------------
23
4
5
6
7
8
9
10
11
12
13
14
15
fig.54
F=(2,72)
- - - - - - - - - - -
~--------------
40
30
- - - Hilbert
..... -
-
.
-
-
-
Z_ordre
- - •• - Peano
20
4
5
6
7
8
9
10
11
12
13
14
15
fig.55
F=(3,48)
34
...............
- - - Hilbert
-
-
-
Z_ordre
24
• • • ••
Peano
- - - - .::.-..=-..==.-:..;=--..-:::::::-:=-=----------
14
4
5
6
7
8
9
10
11
12
13
14
15
fig.56
F=(4,36}
56

---

57
24
- - - Hilbert
-
-
-
Z_ordre
• • • ••
Peano
- - - - - - - ~-:-oo------------------
14
4
5
6
7
8
9
10
11
12
13
14
15
fig.57
F=(6,24)
..
24
~
- ........ ...
... ..... _-- .. --_.
20
16
- - - Hilbert
-
-
-
Z_ordre
• • • ••
Peano
12
3
4
5
6
7
8
9
10
11
12
13
14
15
fig.58
F=(8,18)
28
- - - - - - - - - - : : : - - - - - - - - - - - - - - -
24
20
- - - Hilbert
16
-
-
-
Z_ordre
• • • ••
Peano
.. '"' ......
12
:1
4
5
6
7
8
9
10
11
12
13
14
15
fig.59
F=(9,16)
57

---

58
213
24
-------=-----~~----'....::.-..:.....----'-.......,;--_
........
20
.
16
.
- - - Hilbert
..
-
-
-
Z_ordre
- - • ••
Peano
.. .. .. .. -
.
12 +---+--t---+--t---+----1,.---+----+---f---+--+---+--t---+---1I---
3
4
5
6
7
a
9
10
11
12
13
14
15
fig.50 F=(13,13)
213
24
20
- - - Hilbert
16
-
-
-
Z_ordre
......
- • - ••
Peano
12
3
4
5
6
7
8
9
10
11
12
13
14
15
fig.51
F=(14,14)
90
130
70
- - - Hilbert
60
-
-
-
Z_ordre
• • • ••
Peano
50
40
30
5
6
7
8
9
10
11
12
13
14
15
fig.52
F=(2,98)
58

---

59
....................
45
..............
- - - Hilbert
35
-
-
-
Z_ordre
•• - ••
Peano
........................... '"
25
- - - --::...;-=-=--.=-.---------------
15 +---+--I----+---+--+---+----l,.......--+---+--+---+----l,...---+---+--
4
5
6
7
8
9
10
11
12
13
14
15
fig.63
F=(4,49)
35
- - - - - - _.~-...------------------
..........................
.. .. . .. .. ... .. " ..
25
.
- - - Hilbert
-
-
-
Z_ordre
.......... -
..
• - - _.
Peano
15 +---+--I----+---+--+---+----l,.......--+---+--+---+----l,...---+---+--
4
5
6
7
8
9
10
11
12
13
14
15
fig.64
F=(7,28)
28
-
_
_
-
_
-
-
-
-
-::..;-:;:...:-=-:=-:=-:=-:=-......=-=-................-.......-==........................__
24
20
- - - Hilbert
16
,. .......
. . .
-
-
-
Z_ordre
........... Peano
12
3
4
5
6
7
8
9
10
11
12
13
14
15
fig.65
F=(15,15)
59

---

60
... --._ .... _-_ .... ----_ ..... -
28
----------;>o'--~-------------
24
20
- - - Hilbert
16
---- . .
-
-
-
Z_ordre
• • • ••
Peano
12
3
4
5
6
7
8
9
10
11
12
13
14
15
fig.66
F=(16,16)
- -- -- - -- - -=....:::-=---~------~---~
33
25
- - - Hilbert
• • • ••
Peano
17
3
4
5
6
7
8
9
10
11
12
13
14
15
fig.67
F=(18,18)
. . . . .
'O
. . . .
- - - - - - - - - - - - - ~ ....,: - - - - :.: :...: :-- ..:.......:. -,.: :.: :.: .
34
26
- - - Hilbert
- - - Z-ordre
.--- ..........
......... - Peano
18
4
5
6
7
8
9
10
11
12
13
14
15
fig.68
F=(20,20)
60

---

61
..........................................................
170
150
130
- - - Hilbert
-
-
-
Z_ordre
110
• - - - -
Peano
90
70
6
7
8
9
10
11
12
13
14
15
fig.59
F=(2,200)
90
80
70
..
- - - Hilbert
60
-
-
-
Z_ordre
• • • ••
Peano
50
40
30
5
6
7
8
9
10
11
12
13
14
15
fig.70
F=(4,100)
80
- - - - - - - - -
#
oa
. . . .
. . . . . . .
#
~ .... '
70
60
- - - Hilbert
50
-
-
-
Z_ordre
....... - ......
• • • ••
Peano
40
5
6
7
8
9
10
11
12
13
14
15
fig.71
F=(S,80)
61

---

62
80
...... -
. ... .. .. .. .. ... ..
'"'
...
60
- - - Hilbert
-
-
-
Z_ordre
- - •• -
Peano
.............
40
- - - - -
20
5
6
7
8
9
10
11
12
13
14
15
fig.72
F=(8,50)
50
40
------'-:>--------------------
30
- - - Hilbert
-
-
-
Z_ordre
- - - ••
Peano
20
4
5
6
7
8
9
10
1 1
12
13
14
15
fig.73
F=(10,40)
34
- - - Hilbert
-
-
-
Z_ordre
- - • _.
Peano
26
------:..--------------------
18
4
5
6
7
8
9
10
11
12
13
14
15
fig.74
F=(16,25)
62

---

63
Remarques : Au vu des graphiques ci-dessus, on peut déjà
faire les
remarques suivantes:
1) Quand la taille de la base est petite, pour certaines fenêtres la courbe de
Peano est meilleure que les deux autres. Mais au fur et
à mesure que la taille
augmente, les performances des trois courbes s'égalisent.
2) Pour les fenêtres de forme carrée. la courbe de Peano est meilleure que les
deux autres pour toutes les tailles de la base.
3) Pour les fenêtres de forme rectangulaire "prononcée"
c'est-à-dire que la
longueur est largement supérieure à la largeur, la courbe de Peano est moins
"bonne" que les deux autres.
4) Les performances de la courbe Z-ordre restent constantes quelle que soit la
taille de la base Ceci signifie que cette courbe n'est guère sensible à la position
des fenêtres dans la base.
Par contre, pour les deux autres courbes, le nombre de clusters
ne devient
constant que quand la base atteint
une certaine taille.
A la vue de tout ce qui précède, il paraît intéressant d'étudier le comportement
du nombre de clusters en fonction du rapport de la longueur sur la largeur des
fenêtres pour une taille donnée. On se penchera aussi
sur le nombre moyen de
clusters pour tous les cas possibles.
Nombre minimal de clusters en fonction du rapport Longueur/Largeur
95
75
"
- - - Hilbert
55
-
-
-
Peano
Z_ordre
35
15 -t---+---+----t--I---+---+---+----t--f---+---l---+----;r---+--+--
1,5
4
6,25
16
25
100
fig.75 taille de F=400.
63

---

6-1-
Nombre maximal de clusters en fonction du rapport Longueur/Largeur
180
1
1
140
1
1
1
1
- - - Hilbert
100
1
-
-
-
Peano
60
.... ..
~
20
1,5
4
6,25
16
25
100
fig.76 taille de f=400.
Nombre moyen
de clusters
en fonction du rapport Longueur/Largeur
i.e on prend la
moyenne sur tous les cas.
135
1
1
115
1
1
95
1
1
- - - Hilbert
75
1
-
-
-
Peano
J
55
/
/
35
/
:- - --: -;"~ ..
"'__---..J
15 +---+--+---1-----1---+-_-+__+-_-+__1-_-+-_--1__+-_-+__+-_-+-__
1,5
4
6,25
16
25
100
fig.77 taille de f=400.
4.2.3 Théorèmes
4.2.3.1 Expérience
On choisit une fenêtre quelconque par exemple F=[1 ,6J*[1 ,5], on cherche pour
chaque courbe le nombre de clusters obtenus quand la taille de la base augmente.
64

---

65
13
12
11
1- -
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- -
10
9
8
7
6
5+-------------------------;==--__----,
4
- - - Hilbert
3
2
• • • ••
Peano
1
O+---+---+----l--+---+---+---I--+---+---+----l--+---+---+---I--
3
4
5
6
7
8
9
10
11
12
13
14
15
fig.78
Nombre de cluslers pour la fenêlre F=[1 ,6]*[1 ,5],.
on constate que, pour chaque courbe, le nombre de clusters reste constant
quand la taille de la base augmente.
En fait, on s'aperçoit que ce nombre dépend de la nature des points qui sont
sur le pourtour de la fenêtre, plus
précisément
de
sa frontière au sens
topologique.
fig.79 Nombre de cluslers pour la fenêlre F=[1 ,6] x [1 ,5],.pour la courbe de Hilbert.
On considère les points qui sont sur la frontière de la fenêtre F. Les 20 points
en question sont soit des points d'entrée où la courbe pénètre dans la fenêtre,
soit des points de sortie de la courbe, soit ni l'un, ni "autre. On compte alors 5
points d'entrée(PE) et autant de points de sortie(PS). Or un cluster est en fait une
65

---

GG
paire de points
{e,s} où
e
est un PE
et
s
un P5. D'où un nombre de 5
clusters, ce qui correspond bien au résultat.
····0··············
•••.
0---··.
. ••
fig.81 Nombre de c1usters pour la fenêtre F=[l ,6J·[1 ,51,.pour la courbe de Peano.
On remarque que: soit la courbe parcourt entièrement chaque segment de la
fenêtre parallèle à la largeur formant ainsi un cluster, soit
sur
les autres
segments, on a ( 1/3 +1) groupes de points si 1 est la valeur de la largeur. Ces
groupes peuvent constituer autant de clusters ou moins selon la position de la
fenêtre.
fig.81 Nombre de clusters pour la fenêtre F=[l ,6]"[1 ,5],.pour la courbe z-ordre.
Ici aussi, la nature des points sur la frontière de la fenêtre joue un rôle décisif.
Tous ces points sont soient des points d'entrée, soit des points de sortie. On
obtient donc, en supposant qu'il y a autant de points d'entrée que de points de
sortie, un nombre de clusters égal environ à la somme de la
longueur et de la
largeur.
66

---

67
4.2.3.3 Proposition:Pour chaque courbe, pour une fenêtre F quelconque,
quand la taille de la
base augmente, le nombre
de clusters dans
F reste
constant.
Preuve:Soit 1\\ une des trois courbes. Soit F une fenêtre quelconque dans
la base et soit nbc le nombre de clusters dans F, la taille de la base étant égale
b2m . Quand on augmente la taille de la base, par exemple de m à m+1, alors la
base est divisée en bn parties de taille bnm et F se retrouve tout entière dans une
de ces bn
parties. Or la courbe parcourt entièrement chacune de ces parties
avant de passer à la suivante. Toutes ces parties ont une intersection vide avec la
fenêtre F puisque celle-ci
se retrouve entièrement contenue dans une seule
partie. Alors le nombre de clusters dans F n'a pas varié avec la taille de la
base.
Donc nbc reste constant. C.Q.F.D.
4.2.3.3 Proposition
Pour chaque courbe, en moyenne, le nombre de clusters reste constant
à
partir d'une certaine taille de la base, pour une fenêtre de taille donnée.
Preuve:C'est une conséquence du théorème précédent. A partir d'une certaine
taille de la base, suffisamment grande de façon que la position de la fenêtre au
sein de la base ne soit plus décisif. Puisque la position des fenêtres suit une loi de
distribution uniforme, le cas le plus fréquent sera le cas moyen.
4.2.3.4 Proposition
Pour la courbe de Peano, en moyenne, pour les fenêtres F de taille Co * C1
dans une base de taille 32m , le nombre de clusters est inférieur à Pmax=(C o +
C1) et supérieur à Pmin=(Co + C1) /2 où Co est la longueur du coté parallèle à
l'axe des abscisses et
C celle du coté parallèle à l'axe des ordonnées.. Pour
1
des fenêtres de forme carrée et de coté C, le nombre de clusters est proche de C .
Preuve:On suppose que la taille de la base est la taille minimale nécessaire
pour couvrir la fenêtre. Dans le cas le plus général,
la courbe
se comporte
comme la courbe du serpentin. Le nombre de clusters est égal à la longueur de la
fenêtre.
67

---

En moyenne, puisque les valeurs de la longueur et de la largeur alternent, le
nombre de clusters
devient égal
à (Co + Cl) /2.
Quand
la valeur de
Cl
augmente, le nombre de clusters peut atteindre (Co + Cl) C.Q.F.D.
4.2.3.5 Proposition
Pour la courbe de Hilbert, en moyenne pour les fenêtres F de taille Co * Cl
dans une base de taille 22m, le nombre de clusters est inférieur à Hmax=(Co +
Cl) et supérieur à Hmin=(Co + Cl) /2 où Co est la longueur du coté parallèle à
l'axe des abscisses et
Cl celle du coté parallèle à l'axe des ordonnées.
Preuve:
Le nombre de clusters dépend en fait des points qui sont sur la frontière de la
fenêtre c'est-à-dire son pourtour. Un point sur cette frontière peut être un point
d'entrée de courbe dans la fenêtre, ou un point de sortie, ou ni l'un, ni l'autre. On
peut considérer un cluster comme un doublet constitué d'une entrée et d'une
sortie. Donc il suffit de chercher le nombre des entrées et des sorties pour avoir le
nombre de clusters. Parmi les 2*(Co + Cl) points qui sont sur la frontière de la
fenêtre il y a en moyenne autant de points d'entrée que de sortie. Par ailleurs la
moitié des points n'appartiennent à aucun de ces cas. En effet, les points situés
sur le pourtour qui ne sont pas des points d'entrée/sortie vont toujours par deux.
Alors
on a en
moyenne
(Co + Cl )/2 points d'entrée, (Co + Cl )/2 points de
sortie,donc
(Co + Cl )/2 clusters. Dans les cas défavorables où il y a un déséquilibre en
faveur des points uniquement d'entrée/sortie,le nombre de clusters varie jusqu'à
(Co + Cl )·C.Q.F.D.
4.2.3.6 Remarque:
Yagadish[90) avait émis l'hypothèse que le nombre de clusters soit égal à la
racine carrée de la taille de la fenêtre. Ce qui est loin d'être vérifié pour les
fenêtres de forme rectangulaire.
4.2.3.7 Proposition
68

---

Pour la courbe Z-ordre , en moyenne pour les fenêtres F de taille Co * C, dans
une base de taille 22m, le nombre de clusters est inférieur à Zmax=(Co + Cl) et
supérieur à Zmin=(Co + Cl) /2 où Co est la longueur du coté parallèle à l'axe des
abscisses et
C, celle du coté parallèle à l'axe des ordonnées.
Preuve:
Ici aussi, la géométrie particulière de la courbe z-ordre va jouer un rôle
important. Le nombre de clusters dépend des points qui sont sur la frontière de la
fenêtre. D'abord, du fait de la géométrie de la courbe le nombre de clusters est
peu sensible à la position de la courbe dans la base. Ensuite un point sur deux
situé sur les longueurs forme un cluster(donc Co clusters). Enfin sur chaque
largeur C, on a C,/2
clusters auxquels il faut ajouter C,/2 clusters du fait que la
courbe coupe C,/2 fois chaque largeur.
D'où le résultat.C.O.F.D.
4.2.3.8 Proposition
En dimension 2, pour une taille de fenêtre constante, en moyenne, le nombre
de clusters obtenu avec les courbes de Peano, Hilbert et Z-ordre est proportionnel
au périmètre de la fenêtre.
Preuve:c'est une conséquence des théorèmes précédents.
4.2.4 Analyse du cas le plus favorable
4.2.4.1 Motivation
Parmi les 200 fenêtres figurant dans l'expérience, on considère celle qui réalise
le plus petit nombre de clusters. L'intérêt de ce paramètre est dû au fait qu'avec
certaines distributions de probabilité, notamment une distribution uniforme sur la
diagonale x=y, on peut obtenir une fréquence plus élevée du cas idéal pour tenter
d'obtenir plus fréquemment les positions les favorables.
4.2.4.2 Expérimentations
69

---

70
3
2
r'------rL--I----~_Ordre
o1'--"---------""------
fig.82
fenêtre F=(2,2)
/
10
. /
. /
8
6
. /
4
~
./Z(rdre
2
Hilbert
./peano
o ./
/"
. / . /
fig .84
fenêtre F=(5,5)
/ '
5
. /
. /
4
. /
. /
3
2
Z ordre
Hilbert
V
V
o /
./Peano
. /
. / . /
fig .85 fenêtre F=(6,6)
70

---

71
, /
6
/
/
5
/"
/"
4
/
/
3
Z ordre
2
Hilbert
Peano
1
r
o . /
/
1/
1 / /
fig .86
fenêtre F=(2,18)
, /
B
/
/
7
6
/
/
5
4
Hilbert
3
Z ordre
2
/.
71-
, /
o
/Peano
' /
/ /
fig .87
fenêtre F=(3,1 2)
, /
5
/
/
4
3
/
/l
2
~ ordre
l
Hilbert
Peano
r
o . /
/
/
/ /
fig .88
fenêtre F=(4,9)
71

---

72
10 / '
/ '
/ '
8
/
6
~
~_ordre
4
Hilbert
Peano
2
1
o V
/
/
l / /
fig .89
fenêtre F=(7,7)
10
8
6
4
2
o-l'''--"'------''~---.......----.lC-___r
fig .90 fenêtre F=(8,8)
12 / '
l /
/
10
8
/
~
/
6
Z ordre
4
Hilbert
Peano
r
2
o 1/
1/
1/
/ /
fig .91
fenêtre F=(2,32)
72

---

73
10
8
6
4
2
o~_.l..---_ _----Iol::""-
....IL.
.I'...---r
fig .92
fenêtre F=(4,16)
10 / '
. /
/
8
/
1./
6
/
/ '
4
Z ordre
Peano
2
Hilbert
1
r
o / '
/
/
V /
fig.94 fenêtre F=(1 0,10)
/ '
14
/
/
12
/
10
~
/
8
6
Z ordre
Hilbert
4
Peano
1
r
2
o / '
V
V
V V
fig .95 fenêtre F=(2.50)
73

---

7-l
10
8
6
4
2
o~_.L..-_------"~--_....I'._--_.IoC-----r
fig.96
fenêtre F=(4,25)
24 / '
/
/
16
/
/
z ordre
8
/
Hilbert
/1-
o /
,./peano
V
/ /
fig.97
fenêtre F=(5,20)
20 / '
/
/
16
12
/
8
././
l/Z(rdre
4
Hilbert
Peano
o /
. /
/
/ /
fig.98 fenêtre F=(11, 11)
74

---

75
16
12
B
4
O~_..l..-
""-
----""--
---"''----<
fig ,99
fenêtre F=(12, 12)
24 / '
/
/
20
16
12
/
/ /
/zrrdre
B
Hilbert
4
Peano
1/
1/
o
1/
1 / /
fig .100 fenêtre F=(13,13)
24
16
B
O - ! ' - - - ' - - - - - -.......- - - -......------''''-----r
fig.101
fenêtre F=(20,20)
4.2.4.3 Résultats
Dans la majorité des cas, le clustering réalisé avec la courbe de Hilbert permet
d'avoir les nombres de clusters les plus bas par rapport au clustering réalisé avec
75

---

76
la courbe de Peano, ces deux courbes réalisant de meilleures performances que
la courbe Z-ordre.
4.2.5 Analyse du cas le plus défavorable
4.2.5.1 Motivation
Ce paramètre est encore plus fondamental que le précédent. En effet. dans de
très nombreuses applications, on se préoccupe surtout de ce qui peut arriver dans
le cas le plus défavorable.
4.2.5.2 Expérimentations
./'
12
/
/ '
/
/ '
8
/
1/
Hilbert
Z ordre
4
Peano
1
ï
o /
/
/
/ /
fig .102
fenêtre F=(5,5)
16
8
O.jL-_.L-
""----
----Io~
_____I<"__~
fig.103
fenêtre F=(6,6)
76

---

77
40
30
20
10
O-JoC-_..L-
""'-
----'CC-..-
---"'''--('
fig .104
fenêtre F=(2, 18)
/ '
/
/
24
/
/
16
1/
/
Peano
8
Hilbert
Z_ordre
1
o V
/
/
1 / /
fig.10S
fenêtre F=(3,12)
24
/
/
/
16
/
/
Hilbert
8
Peano
1
.. ordre
o /
/ '
/ '
1 / /
fig.106
fenêtre F=(4,9)
77

---

78
/
24
/
~
~
/
16
Hilbert
Peano
8
Z ordre
ï
1
o . /
/
V
1 / /
fig .107
fenêtre F=(8,8)
/ '
/
/
60
45
/
30
/peano
/
/
15
Hilbert
1
Z ordre
o /
/
/
/ /
fig.108
fenêtre F=(2,32)
/ '
/
/
32
24
/
/
16
Peano
/
/
Hilbert
8
1
Z ordre
o /
/
/
/ /
fig .109
fenêtre F=(4,16)
78

---

79
/ '
32
/
~
/
/ /
/
1/
24
16
Hilbert
Z ordre
Peano
B
ï
1
1/
o
1/
17
17-7
fig. 110
fenêtre F=(1 0,10)
/ '
120
/
; /
BO
/
I./peano
. /
./
40
Hilbert
1
..,' ordre
o ./
/
/ -
. / /
fig.111
fenêtre F=(2,50)
BO / '
/
60
~
~
7
40
Hilbert
Peano
Z ordre
20
1
ï
o l/
/
1/
7 7
fig 112
fenêtre F=(20,20)
79

---

80
500
400
300
200
100
o~_...L..-
- " -
"""'
- - - ' ' - - - - { '
fig 113
fenêtre F=(2,200)
4.2.5.3 Résultats
Ce paramètre n'est guère explicite tant que la forme des fenêtres est plus ou
moins carrée. Dés la forme rectangulaire de celles-là devient prononcée, la courbe
obtient les performances les plus médiocres.
4.2.6 Comportement du nombre moyen de clusters par taille de fenêtre
Pour chaque taille de fenêtre donnée, on fait la moyenne par rapport à toutes
les formes de fenêtres possibles. On étudie alors la moyenne obtenue.
60
55
50
45
40
35
- - - Hilbert
30
-
-
-
Peano
25
20
15
10
5
0
4
10
25
36
49
64
100
144
225
324
400
fig .114
Nombre moyen de clusters en fonction de la taille des fenêtres.
On constate que, tant que la taille des fenêtres reste faible, les performances
des trois courbes restent assez proches. Mais quand la taille des fenêtres devient
80

---

RI
élevée, le nombre moyen de clusters réalisé par la courbe de Hilbert
devient
sensiblement inférieur à ceux réalisés par les deux autres courbes.
4.2.7 Comportement du nombre moyen d'enregistrements par cluster
4.2.7.1 Motivation
Non seulement le nombre de clusters est important mais aussi le nombre de
points
contenus dans chaque cluster. En effet le nombre d'accès-disques
nécessaires
pour chercher un objet spatial dépend du nombre de clusters
contenus dans cet objet mais aussi du nombre moyen de points par cluster. En
effet, si la page est l'unité de transfert entre la mémoire vive et le disque, la taille
de celle-là
joue un rôle important. Par exemple, si un cluster a une taille plus
élevée que la taille de la page, alors il faut plus d'un accès-disque pour l'amener
en mémoire de travail. Nous nous intéressons au nombre moyen de points par
cluster. Il varie de façon inversement proportionnelle à celui du nombre moyen de
clusters..
4.2.7.2 Expérimentations
20
16
12
8
4
O-!L---'------""-------'<C..------"''----('
fig .1154 Nombre moyen de points par cluster pour la fenêtre F=(20,20)
81

---

82
/ '
6
/
/
/
/
4
Hilbert
/
/Z(rdre
2
/peano
o /
/
/ /
fig.116 Nombre moyen de points par cluster pour la fenêtre F=(2,200)
. /
12
/
/
/
. /
10
8
6
Hilbert
/
I/Z ordre
4
ï
2
I/peano
1/
o
. /
V . /
fig .117 Nombre moyen de points par cluster pour la fenêtre F=(4,100)
6
5
4
3
Hilbert
2
O~---'------""'--------"'------"""'--r
fig .118 Nombre moyen de points par cluster pour la fenêtre F=(5,80)
82

---

83
/
15
/
/ '
/ '
/
12
9
6
Hilbert
/ '
l/Z(rdre
3
/,peano
o V
V
V V
fig .119 Nombre moyen de points par cluster pour
la fenêtre F=(S,50
14 /' /
/ '
/
/
12
10
/
V
8
6
Hilbert
Z ordre
4
Peano
1
r
2
o V
/
/
/ /
fig .120 Nombre moyen de points par cluster pour la fenêtre F=(10,40)
4.2.8 Pertinence de la distance
4.2.8.1 Motivation
Depuis Alexandrov[1978], Orenstein[1988] les courbes de Hilbert, Peano, Z-
ordre sont utilisées dans le domaine du clustering. Leur intérêt
vient de leur
propriété de projeter deux points voisins dans l'espace sur des adresses voisines
sur la droite réelle. Rappelons que deux points sont voisins dans l'espace si leur
n
distance de Hamming est égale à
1 c'est-à-dire d(X,y)= L IXi - yil=1 ....si
1
X=(x 1,·······,xn) et Y=(Yl ,...... ,Yn)·
On peut se poser alors la question de savoir si cette propriété peut jouer un
rôle dans la comparaison des performances des trois courbes. Yagadish montra
que ce n'est pas le cas. En effet, si df = sup{ 1f(X) - f(Y)1 / d(X,y)=1 }, il prouve
83

---

que
dh=d = 22m
Qu'en est-il
z
et que
pour chaque ordre d'approximation
m+1
pour la courbe de Peano?
Pour la courbe de Peano pour l'ordre m=1
(voir figures au chapitre 1) on a
d =6=2*3·
p
,
à l'ordre 2 on a dp=54. On montre par récurrence qu'à l'ordre m+1 dp=(6)*32m.
On constate que le rapport dp/dh tend vers l'infini quand m tend vers l'infini. On
peut donc conclure que ce paramètre n'est pas pertinent dans l'étude du c1ustering
comparé des trois courbes.
4.3
COMPORTEMENT
DU
NOMBRE
DE
CLUSTERS
EN
FONCTION DE
LA TAILLE DE LA FENETRE, QUAND LA
TAILLE DE LA BASE EST
CONSTANTE
4.3.1 Motivation
Un second critère fondamental concerne le nombre de clusters obtenu quand
la taille de la fenêtre augmente pour une taille de la base restant constante. Certes
le nombre de clusters augmente alors, mais il est souhaitable
que la
variation
soit la plus faible possible, ceci même si la taille de la fenêtre augmente de façon
exponentielle.
4.3.2 Expérimentations
Il faut tenir compte du fait que les bases n'ont pas les mêmes tailles suivant
que b=2 ou b=3. Pour b=2, on étudie les courbes de Hilbert et de Z-ordre. On
considére successivement les cas où la taille de la base est égale à 29 , puis à 210.
En fait, pour ces deux tailles, les valeurs prises par le nombre de clusters reste
pratiquement constantes. On étudie alors le cas de la courbe de Peano pour la
taille 36 , en sachant qu'on a 29 < 36 < 210. On obtient alors une expérience pour
une taille de la base égale à 36 .
84

---

40,4304
- - - Hilbert
35,3766
,... - -'
30,3228
- - - - -
Peano
25,269
20,2152
...
. . .
....
.
15.1614
. ..
. . .
. . '
...
10,1076
.. -
5,0538
0
4
10
25
36
49
64
100
121
144
169
196
225
256
289
324
369
400
fig.121 Comportement du nombre de clusters en fonction de la taille de la fenêtre quand la
taille de la base= 36. Seules les
fenêtres de forme carrée sOnt considérées.
On considère un second cas avec 214<311<215.
De la taille 2 14 à la taille 2 15 ,
le nombre de clusters reste encore inchangé pour une même taille de la fenêtre.
On peut donc dire qu'il en de même pour la taille 311 .
40,4304
- - - Hilbert
35,3766
-
-
-
Z_ordre
30,3228
Peano
25,269
20,2152
15,1614
10,1076
5,0538
0
4
10
25
36
49
64
100
121
144
169
196
225
256
289
324
369
400
fig.122 Comportement du nombre de clusters en fonction de la taille de la fenêtre quand la
taille de la base= 311 . Seules les fenêtres de forme carrée sOnt considérées.
On considère un troisième cas avec 219<314<220
85

---

86
40,4304
- - - Hilbert
35,3766
30,3228
- - - - -
Peano
25,269
20,2152
15,1614
10,1076
5,0538
0
4
10
25
36
49
64
100
121
144
169
196
225
256
289
324
369
400
fig.123 Comportement du nombre de clusters en fOnction de la taille de la fenêtre quand la
taille de la base=3 14
Seules les fenêtres de forme carrée sOnt considérées.
Toutes les figures ont la même allure.
Nous pouvons énoncer le résultat
suivant.
4.3.3.Théorème
Quand la taille de la base est constante, pour les 3 courbes, le nombre de
clusters varie de façon proportionnelle à proportionnelle au rapport .6(8) / .JS.
quand la taille de la fenêtre augmente.
Preuve: On se restreint sans perte de généralité aux fenêtres de forme carrée.
Pour chaque fenêtre carrée de coté c, nous avons vu que le nombre de clusters
dépend linéairement de c, on a nbc=u·c + v , si nbc est le nombre de clusters, u
et v étant des constantes réelles. Donc on a
6(nbc)=u(6C) or on sait c=.JS si
8 est la taille de la fenêtre. On obtient alors
6(nbc)=u 6(8) / 2.JS.
Donc
quand la taille 8 de la fenêtre augmente,
la variation de nbc
est
proportionnelle au rapport 6(8) / .JS.
4.4 CONCLUSION
A ce stade de notre étude, on
peut dire que pour les trois courbes, le nombre
de clusters obtenus pour une fenêtre F dépend de la nature des points qui sont
situés sur sa frontière, plus exactement qu'en moyenne ce nombre varie entre
86

---

X7
(Co +C,)/2 et
(Co +C,) si Co et C, sont les cotés de la fenêtre. Le nombre de
clusters dépend aussi de la position de la fenêtre dans la base, mais cette
dépendance devient négligeable en moyenne quand la taille de la base devient
élevée. Au contraire de la dépendance par rapport à la forme de
la fenêtre. En
effet, le nombre de points sur la frontière dépend de la forme (carrée ou
rectangle). On peut constater que, pour les fenêtres de forme carrée, la courbe de
Peano réalise de meilleures performances que la courbe de Hilbert. Mais. dès que
la forme des fenêtres devient rectangulaire, c'est le contraire qui se produit.
Donc ,en dimension 2, on ne peut guère conclure
qu'une des 2 courbes est
meilleure que l'autre
Peut-être le passage à des dimension supérieures nous
permettra-t-il de conclure?
87

---

CHAPITRE 5 CLUSTERING EN DIMENSION N > 2
5.1.INTRODUCTION
Aucune étude, à notre connaissance n'a été effectuée dans le domaine du
clustering en dimension n >2.
Même si les calculs ne sont pas coûteux en temps machine du fait que
l'algorithme n'examine
pas les parties
qui ne rencontrent pas la fenêtre, nous
nous limitons
à 100 cas par expérience. Allons-nous retrouver les mêmes
constatations qu'en dimension 2?
5.2.CLUSTERING EN DIMENSION 3
5.2.1.COMPORTEMENT DU NOMBRE DE CLUSTERS EN FONCTION DE
LA TAILLE DE LA BASE
5.2.1.1 Résultats' expérimentaux
Les expériences sont faites sur 100 cas. On mesure le nombre de clusters
quand la taille de la base augmente. En abscisse, on prend le logarithme décimal
de cette taille;
15
13
- - H i l b e r t
11
-
-
-
Peano
9
,---~~--------------
7
5+---+----+--1----+---+----1--+---+---+--+----+---+---1--
2
3
4
5
6
7
8
9
10
fig.124
Fenêtre F =(3,3,3)

---

89
30
25
- - - Hilbert
-
-
-
Peano
Z_ordre
20
.......
'~~~ ~~--------------
15 +---f-----l---+---+---+---+-----l---+---+---+---+-----il----+-
2
3
4
5
6
7
8
9
10
fig.125 Fenêtre F=(4,4,4)
50
.............. ..... _ ........ _-_ .. _--_ .. __ .. __ ..... _-_ ........ -
40
- - - Hilbert
-
-
-
Peano
Z_ordre
30
....... ,
- - - - - - - - - - - - - - - - - - -
20 +---f-----l---+---+---+---+-----lr----+---+---+---+-----il----+--
2
3
4
5
6
7
8
9
10
fig.126 Fenêtre F=(5,5,5)
100
90
80
- - - Hilbert
70
-
-
-
Peano
60
Z_ordre
50
40
30
2
3
4
5
6
7
8
9
10
fig.127 Fenêtre F=(6,6,6)
89

---

90
90
80
70
- - - Hilbert
-
-
-
Peano
60
Z_ordre
50
40
2
3
4
5
6
7
8
9
10
fig.12B Fenêtre F=(7,7,7)
160
140
120
- - - Hilbert
'
__
.
-
-
-
Peano
Z_ordre
100
80
- - - - - - - - - - - - - - - - - - -
--
60
2
3
4
5
6
7
8
9
10
fig.129 Fenêtre F=(B,B,B)
150
130
1
- - - Hilbert
1
1
-
-
-
Peano
110
1
Z_ordre
1
1
90
1
- __1
70
2
3
4
5
6
7
8
9
10
fig.13D
Fenêtre F=(9,9,9)
90

---

91
240
220
200
- - - Hilbert
180
-
-
-
Peano
160
Z_ordre
140
120
100
- - - - - - - - - - - - - - - - - - - -
80
2
3
4
5
6
7
8
9
10
fig131
Fenêtre F=(1 0,10,10)
150
...... -
-
..
130
1
1
- - - Hilbert
1
-
-
-
Peano
110
1
,
Z_ordre
1
1
90
- --'
70
2
3
4
5
6
7
8
9
10
fig.132 Fenêtre F=(4,10,25)
240
220
-
__
..
200
- - - Hilbert
180
-
-
-
Peano
160
Z_ordre
140
......
...... _-----------------
120
100
3
4
5
6
7
8
9
10
fig133
Fenêtre F=(11,11,11)
91

---

92
410
370
330
- - - Hilbert
290
-
-
-
Peano
................. --
.
Z_ordre
250
210
170
- - - - - - - - - - - - - - - - - -
130
3
4
5
6
7
8
9
10
fig134
Fenêtre F=(12.12.12)
240
- - - Hilbert
-
-
-
Peano
Z_ordre
160
80
5
6
7
8
9
10
fig.135
Fenêtre F=(3.12.48)
92

---

93
400
350
...
-
.. - .. -._----
~
_
-
300
- - - Hilbert
-
-
-
Peano
250
Z_ordre
200
- - - - - - - - - - - - - - - - - - - -
150 +----+----1---+----+---+-----.,f----+--+----!---+---+---+-,
3
4
5
6
7
8
9
10
fig.136 Fenêtre F=('3,'3,'3)
5.2.1.2
Remarque:
On constate que cette fois-ci.
la courbe de Peano donne de meilleures
performances que la courbe de Hilbert, et pour toutes les formes de fenêtres.
qu'elles soient cubiques ou non.
5.2.1.3 Propositions
On peut énoncer les résultats suivants.
5.2.1.3.1 Proposition
Pour la courbe de Peano, pour les hypercubes de taille Co*C, *Cz", ....le nombre
de c1usters est égal en moyenne à ((Co + C,)/2) * Cz quand la taille de la base
augmente. Dans le cas particulier de fenêtres de forme cubique de taille C * C *
C , le nombre de clusters devient égal à C2.
Preuve:On a vu qu'en dimension 2, le nombre de c1usters
est égal en
moyenne à
((Co + C,)/2) dans les cas les plus favorables, en particulier pour les fenêtres
de forme carrée.
Pour chaque fenêtre de dimension 3, la courbe de Peano remplit l'hypercube
en parcourant entiérement et successivement chaque surface {hl x [Co' C,J. pour
93

---

9.+
h=O,1 ,..... ,C2. Donc le nombre de clusters total est égal au nombre de clusters par
surface que multiplie la hauteur C2. D'où le résultat.
C.Q.F.D
5.2.1.3.2 Proposition
Pour la courbe de Hilbert, pour les hypercubes de taille Co*C 1*C2 , le nombre
de clusters est égal à 2*(Co*C
*C
1 + Co*C 2 + C1
2)/4. Pour un cube de coté C, ce
nombre devient (3*C2)/2.
Preuve:Le nombre de clusters dépend comme en dimension 2 du nombre de
points sur la frontière de l'hypercube. Ici, celle-ci est constituée par les six faces
de l'hypercube dont la surface totale est égale à
2*(Co*C1 + Co*C2 + C1*C2).
En supposant qu'il y a autant de points d'entrée de la courbe dans la fenêtre que
de points de sortie et que la moitié des points sur la frontière n'en sont pas, on a
le résultat.
5.2.1.3.3 Proposition
Pour la courbe Z-ordre , pour les hypercubes de taille Co*C *C
1
2, ,le nombre de
clusters est égal à 2*(Co*C + Co*C
*C
1
2 + C1
2)/4.
Pour un cube de coté C, ce nombre devient
(3*C2)/2.
Preuve: Comme dans le cas de la courbe de Hilbert, le nombre de clusters
dépend du nombre de points d'entrée/sortie sur la frontière de la fenêtre. Et avec
les mêmes hypothèses on obtient le même résultat.
5.2.1.3.4 Proposition
En dimension 3, quand la taille de la base varie, la courbe de Peano réalise de
meilleures performances que celle de Hilbert et de la courbe z-ordre dont les
performances sont similaires.
Preuve:C'est une conséquence des théorèmes précédents. En effet, pour des
fenêtrés de forme cubique, on a
nbc= C2
pour Peano
et
nbc=( 3*C2)/2
pour Hilbert et z-ordre.
94

---

95
Dans le cas général des fenêtres de forme quelconque
le
résultat reste le
même car
nbc=«Co + C,)/2) * C2 =(Co 'C2 + C, * C2)/2
pour Peano
et
nbc=
5.2.2.COMPORTEMENT DU NOMBRE DE CLUSTERS EN FONCTION DE
LA TAILLE DE LA FENÊTRE
5.2.2.1 Résultats expérimentaux
160
- - Hilbert
110
-
-
-
Peano
60
1 0 ~'::"":=--+--+--~f----+---+-----+--+-----1f----+--+----+--+---
27
64
125
144
343
512
729
1000
fig.'37 Taille de la base=2'8=3'2
5.2.2.2 Remarque
Pour toutes les tailles de bases fixées, les courbes ont la même allure que la figure précédente.
5.2.2.3 Proposition
En dimension 3, pour les 3 courbes, quand la taille de la base est constante,
le nombre de clusters varie
proportionnellement à
t. V/W )
si V
est la taille
de la fenêtre.
Preuve:C'est lune preuve similaire à celle donnée en
dimension 2. Le nombre
de clusters est proportionnel à C2 pour une fenêtre cubique de côté C et de taille
V=C3 d'où t. V=3*C2 t.C. On en déduit que
t.(nbc)=u*t.(C2) d'où
t.(nbc)=(2/3)* (t.v/W).
5.3.CLUSTERING EN DIMENSION 4
95

---

96
5.3.1.COMPORTEMENT DU NOMBRE DE CLUSTERS EN FONCTION DE
LA TAILLE DE LA BASE
5.3.1.1 Résultats expérimentaux
Les expériences sont faites sur 30 cas. On ne considére que les hypercubes de
coté constant C
car on a remarqué qu'en dimension 3. la forme des fenêtres ne
joue plus un rôle décisif dans la comparaison des différentes fenêtres.
45
- - - - - - -
40
.. .. .. .. ... .. ... .. .. .. .. .. .. . .. .. r·--::' ..--: .. .. .. .. .. .. .. .. .. .. .. .. ..
/
/
- - - Hilbert
35
/
/
-
-
-
Peano
/
30
/
'-
/
' - /
25
20 +-__+-_ _+-_ _+-_ _+-_ _+-_ _+-_ _+-__+-__+-__+-__+-__
4
5
6
7
8
9
10
fig.138
Fenêtre F =(3,3,3.3)
170
140
- - - Hilbert
110
-
-
-
Peano
. , , - - - - - - - - - - - - -
80
/ '
/ '
/ '
50
4
5
6
7
8
9
10
fig.139
Fenêtre F =(4,4,4,4)
96

---

97
210
170
- - - Hilbert
/ - - - - - - - - - - - - -
-
-
-
Peano
/
/
/
130
/
/'
/'
/'
90 +----t----t---+---+---+---+---+---+---+---t---t--
4
5
6
7
8
9
10
fig.14D
Fenêtre F =(5.5,5,5)
600
500
- - - Hilbert
400
-
-
-
Peano
300
/ ' - - - - - - - - - - - -
/'
.....
/'
.......... /'
200
4
5
6
7
8
9
10
fig.141
Fenëtre F =(6,6,6,6)
...
..
..
540
- - - Hilbert
r - - - - - - - - - - - -
-
-
-
Peano
/
440
\\
/
\\
/
\\
/
\\
/
\\ /
340
4
5
6
7
8
9
10
fig.142
Fenêtre F =(7,7,7,7)
97

---

98
1500
... "' ......... _--- ... __ ... _---_ ...... _ .......
- - - Hilbert
1000
-
-
-
Peano
Z_ordre
, / - - - - - - - - - - - -
, /
, /
, /
. /
. /
. /
500
4
5
6
7
8
9
10
fig.143
Fenêtre F =(8,8,8,8)
1300
- - - - - - - - - - - -
1
- - - Hilbert
1
1
-
-
-
Peano
1
1100
Z_ordre
1
j
/
/
/
/
900
4
5
6
7
8
9
10
fig.144
Fenêtre F =(9,9,9,9)
3000
2500
.......................................................... ,
- - - Hilbert
-
-
-
Peano
2000
Z_ordre
/
/
1500
/
, /
, /
, /
, /
1000
4
5
6
7
8
9
10
ig.145
Fenêtre F =(10,10,10,10)
5.3.1.2 Propositions
98

---

99
5.3.1.2.1. Proposition
En dimension 4, en moyenne, le nombre de clusters pour la courbe de Peano
pour les fenêtres de taille C * C * C * C est égal
à
C3.
Preuve:De la même façon qu'en dimension 3, le nombre de clusters total est
égal au nombre de clusters en dimension 3 que multiplie la valeur du
coté de
l'hypercube. D'où le résultat.
5.3.1.2.2.
Proposition
En dimension 4, en moyenne, le nombre de·c1usters pour la courbe de Hilbert
pour les fenêtres de taille C * C * C * C est égal
à
2*C3
Preuve:Le nombre de clusters dépend de la frontiére de l'hypercube. Or la
frontière d'un hypercube de dimension 4
est composé de 8
hyperplans de
dimension 3. d'où le résultat.
5.3.1.2.3.
Théorème
En dimension 4, en moyenne, le nombre de clusters pour la courbe de Z-ordre
pour les fenêtres de taille C * C * C * C est égal à
2* C3 .
Preuve:C'est exactement la même démonstration que
pour
la courbe
de
Hilbert.
5.3.2.COMPORTEMENT DU NOMBRE DE CLUSTERS EN FONCTION DE
LA TAILLE DE LA FENÊTRE QUAND LA TAILLE DE LA BASE EST
CONSTANTE.
5.3.2.1 Résultats expérimentaux
99

---

100
2120
1420
-.~.-
Hilbert
-
-
-
Peano
....
....
/'
720
/ '
/
/ '
.... --
20 i""=:oi=...=+=---+----t---+---t----+---t---+--+-----l---+---t----1
81
256
625
1296
2401
4096
6561
10000
fig.l46 Taille de la base=224=314
5.3.2.2 Remarque
Pour toutes les tailles de bases fixées, les courbes ont la même allure que la figure précédente.
5.3.2.3 Théorème
En dimension 4, pour les 3 courbes, quand la taille de la base est constante, le
nombre de clusters varie propertionnelle
à
1\\V/W si V est la taille de la
fenêtre.
Preuve:C'est une preuve similaire à celle donnée en dimension 3.
5.4.CLUSTERING EN DIMENSION
N>4
5.4.1.COMPORTEMENT DU NOMBRE DE CLUSTERS EN FONCTION DE
LA TAILLE DE LA BASE.
Théorème:Pour toute dimension N > 2, le nombre de clusters obtenus avec
la courbe de Peano est égal à
Cn-l. Ce nombre est (n/2)*cn-l
pour les courbes
de Hilbert et Z-ordre.
Plus
n augmente,
plus la courbe de Peano devient plus efficace que les
deux autres courbes.
Preuve: Pour toute
dimension n
> 2 , pour un hypercube de coté C , le
nombre de clusters pour la courbe de Peano est égal à cn-l. Pour Hilbert, ce
100

---

10 l
nombre est égal à (2*n)*C n-1/4. En effet, pour un hypercube de dimension n, le
nombre de points sur la frontière est égal (2*n) *cn-1 où (2*n) est le nombre
d'hyperplans de dimension n-1 et de volume cn-1.
5.4.2.COMPORTEMENT
DU
NOMBRE
DE
CLUSTERS
EN
FONCTION DE LA TAILLE DE LA FENÊTRE
Théorème:Pour toute dimension n > 2 , pour toute courbe, quand la taille de
la fenêtre augmente, le nombre de clusters augmente de façon proportionnelle à
6V/W
si
V est la taille de la fenêtre.
Preuve:Exactement, comme en dimension
3.
5.5 CONCLUSION
Alors qu'en dimension 2, il est difficile de comparer les performances des trois
courbes, dès qu'on passe en dimension n > 2, la courbe de Peano devient plus
efficace que les deux autres. Et ceci est d'autant plus vrai que n est grand. Les
expérimentations confirment ces résultats. En plus, pour toutes les trois courbes,
quand la taille V de la base varie alors le nombre de clusters varie aussi de façon
proportionnelle à
6 V/W .
101

---

chapitre 6
CONCLUSIONS ET PERSPECTIVES
L'utilisation des courbes remplissant l'espace pour le regroupement des
données en analyse des données date des années 70. Ces courbes sont aussi
utilisées pour le regroupement des données dans le domaine des bases de
données spatiales depuis le milieu des années 80. Et l'intérêt dans ce domaine
n'est
toujours
pas
retombée.
Jusqu'ici
(conférer
l'état
de
l'art
dans
Yagadish[1990]), parmi
les différentes courbes remplissant l'espace proposées,
celle de Hilbert semblait la plus efficace . Pourquoi?
Mis à part
des calculs
expérimentaux effectués uniquement en dimension n= 2 aucune explication
analytique n'était venue jusqu'ici prouvé cette assertion.
Nous avons
introduit, parmi les courbes
proposées celle de Peano., en la
comparant à la courbe de Hilbert et à celle dite z-courbe.
Pour toute dimension n, nous montrons que, pour les trois courbes, le nombre
de clusters obtenus quand la base augmente pour une fenêtre de taille fixée
dépend en fait des points sur la frontière de cette fenêtre. Si, en dimension 2, les
performances des courbes de Peano et Hilbert sont équivalentes, ce n'est plus le
cas dès que la dimension devient supérieure à 3. En effet, pour les hypercubes
de coté C constant, si nbc est le nombre de clusters, alors nbc=Cn-1
pour la
courbe de Peano et (n/2)*Cn-1 pour celles de Hilbert et
z-courbe. Les calculs
expérimentaux effectués
en dimension 2, 3 et 4
confirment ces formules
analytiques. Pour toutes ces trois courbes, la variation du nombre de clusters par
rapport
à la taille V
des
fenêtres est proportionnelle à
ô V/W.
Ainsi donc, nous avons pu donner une formule analytique pour déterminer le
nombre de clusters obtenus par les trois courbes non seulement en dimension 2,
mais aussi en toute dimension n > 2. Ce qui nous a permis de prouver que la
courbe de Peano est plus efficace que les deux autres courbes. Mieux, lorsque la
dimension
n
tend
vers l'infini, le rapport
nbch/nbcp tend aussi vers l'infini si

---

103
nbcp=nombre de clusters pour la courbe de Peano et nbch=nombre de clusters
pour la courbe de Hilberi.
Ce travail a été abordé dans le cadre du clustering dans les bases de données
spatiales. Comment
le modèle de regroupement linéaire que nous avons utilisé
intègre-t-il
la dynamicité pour prendre en compte les mises-à-jours fréquentes
dans certaines applications? c'est le travail que nous proposons d'aborder
ultérieurement.
+-
103

---

Programme C pour l'algorithme de clustering pour la courbe de Hilbert
typedef int ta[1 00];
typedef int tableau[20][20];
typedef unsigned long int pa[20]; typedef struct
{
pa u;
pa v;
} fenetre;
typedef struct hypercube
{
int *pstatut;
float *pnumdebut;
unsigned long int *pcote,*psommet;
}*phyp;
typedef struct cellule
phyp pobj;
struct cellule *psuiv;
} *element;
typedef struct tete
element prem,vue,der;
} *Iiste;
typedef unsigned long int nbc[201]; const int b=2,NMAX=200;
float pfloat[100],xO=0;
fenetre f;
int i,j,n=2,m,l,jxO,N,uO=0;
liste LTO,L;element e;unsigned long int M;
phyp H;
flcat uu,uv;
unsigned long int a[20],c[20],pc,surface,u,umax,umin; nbc nbcp,nb;
FILE *fic;
unsigned long int puissance(int m)
{
int i;
unsigned long int pu;
pu=1 ;
for(i=1 ;i<=m;i++) pu=b*pu;
return pu;
}
float puissancefloat(int m)
{
int i;
float pu;
pu=1 ;
for(i=1 ;i<=m;i++) pu=b*pu;
return pu;
}
int pprinc1 (tableau x)

---

105
{lion calcule j1
if(x[n-1][0]==1) return n-2;
else ifUxO==O) return n-1;
else ifUxO==n-1) return n-1;
else return jxO-1;
}
int revposprinc(ta t)
{lion calcule la pos. princ. d'un vecteur t;
int j,ia,jj;
ia=t[n-1];
j=n-2;
while( (tlJ]==ia) && U>=O) ) j--;
ifU==-1) jj=n-1 ;
else jj=j;
return jj;
}
float revhilbert(pa y1)
{
lion calcule x à partir de y;
ta tt,ttt,TT; tableau xX,RAU,SIGMA,TAU,TAUT;
int i,j,k=0,kk=0,10".J[40]:unsigned long int u=O;float uu=O;
forU=O;j<n ;j++)
{
u=y1 m;
for(i=O;i<m;i++)
xx[jUm-1-i] = (int)u % b;
u=u 1 b;
}
}
Il en sortie on a xx;
forU=O;j<n;j++) tt[j]=xx[j][O];
jxO=revposprincOQ:
J[0]=pprinc1 (xx);
Ili=O;
forU=O;j<n ;j++) {TAUT[j][O]=xx[j][O];TAUm [O]=xx[j][O];S IGMA[j][O]=xx[j][O];}
RAU[O][O]=SIGMA[O][O];
forG=1 ;j<n;j++) {RAU[j][0]=SIGMA[j][0]"RAU[j-1 ][O];}
Il i>=1 ;
for(i=1 ;i<m;i++)
{
forU=O;j<n;j++) {TAUT[j][i]=xx[j][i]"xx[j][i-1];}
k=k+J[i-1 ];
forG=O:j<n;j++) {TAU[j][i]=TAUT[(G+n-k)%n)][i];}
forU=O;j<n;j++) {SIGMA[j][i]=TAU[j][i];}
kk=n-J[i-1]-1 ;
SIGMA[O][i]= 1-SIGMA[OHi];SIGMA[kk][i]=1-SIGMA[kkHi];
RAU[0][i]=SIGMA[0][i]"RAU[n-1 ][i-1];
forU=1 ;j<n;j++) {RAU[j][i]=SIGMAIj][i]"RAU[j-1][i];} forG=O;j<n;j++) tttm=RAU[j][i];
J[i]=revposprinc(ttt);
}
for(i=O;i<m;i++)
{
10=i*n;
105

---

106
forU=O;j<n;j++) TT[IO+j]=RAUUHi];
}
for(i=O;i<l;i++) uu=uu + pfloat[I-1-i]*TT[i];
return uu;
}
jj Creation d'une cellule tete de liste
liste creerO
{
liste ItO;
ItO= (1 iste) maIl oc(sizeof(struct tete));
ItO->prem=NULL;ltO->vue=NULL;ltO->der=NULL;
return ItO;
}
j* Test de fin de liste
static int fin(liste L)
{
return (L->vue==NULL);
} *j
1* Positionnement de la vue en première position *j void premier(liste L)
{
L->vue=L->prem;
}
j* Positionnement de la vue en derniere position *j void dernier(liste L)
{
L->vue=L->der;
}
1* Positionnement de la vue sur l'element suivant *j void suivant(liste L)
{
if(L->vue)
L->vue=L->vue->psuiv;
else printf("erreur element suivant");
}
element precedent (liste LI)
{
element q;
q=(element)malloc (sizeof (struct cellule));
q = L1->prem;
if (q==L1->vue)
return (NULL);
else {
while (q->psuiv !=L1->vue)
q=q->psuiv; }
return (q);
}
1* element copier(element e)
{
element p,q;phyp H; H=(phyp)malloc(9*(sizeof(struct hypercube)));
p=(element)malloc(sizeof ( struct cellule)); q=(element)malloc(sizeof ( struct cellule));
H->statut=e-> po bj->statut; H->cote=e-> po bj->cote;
H->sommet[O]=e-> pobj->sommet[O]; H->sommet[1]=e->pobj->sommet[1]; q=(e-
>psuiv);
p->psuiv=q;
p->pobj=H;
return p;
106

---

107
}*I
1* Remplacement de la vue de la liste L par une sous-'iste LL *1
liste remplaceliste(liste L,liste LL)
{ liste Itemp;element e1 ,e2;
Itemp=creerO;
if(L->vue==L->prem) /* insertion en premiSre position *1
{
Itemp-> prem= LL-> prem;
Itemp->vue=LL->prem;
LL->der->psuiv=L->vue->psuiv;
free(L->vue) ;
Itemp->der=L->der;
premier(ltemp);
return Itemp;
}
else if(L->vue==L->der) 1* insertion en dernière position *1
{
e1 =(element)malloc (sizeof (struct cellule»; e1 =precedent(L);
Itemp->prem=L->prem;
Itemp->der=LL->der;
Il L->vue=e1;
Il
L->vue->psuiv=LL->prem;
e1->psuiv=LL->prem;
Itemp->vue=LL->prem;
free(L->vue);
return Itemp;
}
else
/* sinon
*1
{
e1 =(element)malloc (sizeof (struct cellule»; e2=(element)malloc (sizeof (struct
cellule»; e1 =precedent(L);
Il suivant(L);
Il e2=L->vue;
Il L->vue=e1 ;
Il L->vue->psuiv=LL->prem;
Il L->vue=e2;
e2=L->vue->psuiv;
e1->psuiv=LL->prem;
LL->der->psuiv=e2;
Il LL->der->psuiv=L->vue;
Itemp->prem=L->prem;
Itemp->der=L->der;
Itemp->vue=LL->prem;
free(L->vue) ;
return Itemp;
}
}
1* void swapelem(element ip,element iq )
{
element ptemp, ph;
ptemp=(element) malloc(sizeof (struct cellule»; ph=(element) malloc(sizeof (struct
cellule»; ptemp=ip->psuiv;
ph->pobj=ip->pobj;
107

---

108
ip->psuiv=iq->psuiv;
ip->pobj=iq->pobj;
iq->psuiv=ptemp;
iq-> pobj= ph->pobj;
free(ph) ;free(ptemp);
} *1
void swapelem(element ip,element iq )
{ phyp pt;
pt=(phyp) malloc(sizeof (struct hypercube»;
pt=ip->pobj;
ip->pobj=iq->pobj;
iq->pobj=pt;
Il free(pt);
}
void swapi(unsigned long int *ip,unsigned long int *iq )
{ unsigned long int temp;
temp=*ip; *ip=*iq; *iq=temp;
}
void swapfloat(float *ip,float *iq )
{ float temp;
temp=*ip; *ip=*iq; *iq=temp;
}
liste triselection(phyp HH)
{
float a[5];llunsigned long int *a;
liste Itemp;
int i,j,min,ii;element *ee;
Itemp=creerO;
Ilfor(i=0;i<1 O;i++) a[i]=(int) malloc(sizeof (int»;
Ila=(unsigned long int*) malloc(11 *sizeof (int»; ee=(element *) malloc(1 O*sizeof (struct
cellule»;
for(i=O;i<N;i++) ee[i]=(element ) malloc(sizeof (struct cellule»;
if(ee==NULL) printf("probleme de memoire sur ee");
/*if( sizeof(*ee)<g*sizeof(struct cellule» printf("probleme de memoire sur ee\\n");*1
for(i=O;i<N;i++) a[i]=*(HH[i]. pnumdebut);
ee[N-1 ]->pobj=&HH[N-1 ];ee[N-1 ]->psuiv=NULL;
for(i=N-2;i>0;i--)
ee[i]->psuiv=NULL;
ee[i]->pobj=&HH[i];
}
ee[O]->psuiv=NULL;
ee[O]-> pobj=&H H[0];
for(i=0;i<N-1 ;i++)
min=i;
forU=i+1 ;j<N;j++) {if (a[j] < a[min]) min=j;}
Iiswapi(&a[min],&a[i]);
swapfloat(&a[min],&a[i]);
swapelem(ee[min],ee[i]);
}
for(i=0;i<N-1 ;i++)
ee[i]-> psuiv=ee[i+1]; Itemp->prem=ee[O];ltemp->vue=ee[D];ltemp-
>der=ee[N-1 ];
return Itemp;
108

---

109
}
liste eclatement( phyp H)
{
int ii,jj,i=O;liste Itemp;phyp HH;pa yy;
HH=(phyp)malloc(S*sizeof( struct hypercube));
if(*(H->pcote)==1) return NULL;
else
{
for(ii=O;ii<b;ii++)
{
forUj=O;jj<b;jj++)
{
HH [i]. pstatut=(int*)malloc(sizeof(i nt»; *(H-> pstatut)=O;
HI-Hi]. pnu mdebut=(float*) ma Iloc(sizeof(float»;
HH[i].psommet=(unsigned long int*)malloc(2*sizeof(unsigned long int»;
HH[i].pcote=(unsigned long int*)malloc(sizeof(unsigned long int»;
yy[O]=HH[i].psommet[O]=H->psommet[O]+ii*( *(H->pcote)/b);
yy[1 ]=HH[i].psommet[1 ]=H->psommet[1 ]+jj*( *(H->pcote)/b);
*(HH[i]. pnu mdebut)=revhilbert(yy);
*(HH[i].pcote)= (*(H->pcote»/b;
*(HH[i] .pstatut)=O;
î++;
}
Item p=creerO;
Item p=triselection(H H);
return Itemp;
}
int intersection(phyp H,fenetre f)
{ pa y;int i=O,j,ui=O;unsigned long int cote;
forU=O;j<n;j++) yU]=H->psommetU];
cote=*(H->pcote);
while( (n-i) && (f. u[i]<=y[i]) && (y[i]+cote-1 <=f. v[i]-1) ) i+=1;
if(i==n) return 1;
for(i=O;i<n;i++){ if ( (f.v[i]-1 <y[i]) Il (y[i]+cote-1 <f.u[i])
ui+=1;} if(ui) return 2;
else return 0;
}
liste traitervue(element e, fenetre f)
{
liste LU;
LU=creerO;
LU=eclatement( e->pobj );
premier(LU);
while(LU->vue)
{
*(LU->vue-> pobj-> pstatut)= intersection(LU->vue-> pobj. f); suivant(LU);
}
premier(LU);
return LU;
}
liste traitementliste(liste L,fenetre f)
{
liste Up,LL;element elt,eltO;
109

---

110
elt=(element)malloc(sizeof ( struct cellule));
elto=(element)malloc(sizeof ( struct cellule)); ltp=creerO;LL=creerO;!/ltp=creerO; ltp-
>prem=L-> prem; Ltp->vue=L-> prem; Ltp->der= L->der; L-> vue=L-> prem-> psuiv;
eltO=Ltp->prem; while(L->vue){eltO->psuiv=L->vue;suivant(L);elto=elto->psuiv;}
elt=Ltp->prem;
while(elt)
{
if( (*(elt->pobj->pcote)==1)11( *(elt->pobj->pstatut)==1)11( *(elt->pobj->pstatut)==2) )
elt=elt->psuiv;
else
{
LL=traitervue(elt, f);
Ltp->vue=elt;
Ltp=remplaceliste(Ltp,LL);
elt=Ltp->vue;
return Ltp;
}
void shellsort(nbc aX,int N)
{
int i,j,h;unsigned long int v;
for(h=1 ;h<=N/9;h=3*h+1);
for(;h>O;h/=3)
{
for(i=h+1 ;i<=N;i++)
{
v=ax[i];j=i;
while( U>h) && (ax[j-h]>v) ) {ax[j]=ax[j-h];j-=h;}
ax[j]=v;
}
Il Fonction de test d'une liste vide
static int nulle(liste L)
{
return (L->prem==NULL);
}
void detruireobjet(phyp H)
{
free(H->psommet);
free(H-> pstatut);
free(H-> pn umdebut);
free(H->pcote) ;
Ilfree(H);
}
void detruireliste(liste L)
{
L->vue=L->prem;
while(L->vue)
detru ireobjet(L->vue-> pobj);
L->prem=L->vue;
L->vue=L->vue-> psuiv;
110

---

111
free(L->prem);
}
L-> prem=L->der=NULL;
}
mainO
{
fic=fopen("1 b.dat", "a+");
Ilfprintf(fic,"n
m
c=
nbcp
moyp\\n");
N=(int) pu issance(n);
H=(phyp)m alloc(sizeof(struct hypercube)); H-> pstatut=(int*)malloc(sizeof(int)); H-
>pstatut=&uO; H->pnumdebut=(float*)malloc(sizeof(float)); H->pnumdebut=&xO; H-
>psommet=(unsigned long int*)malloc(2*sizeof(unsigned long int)); H-
>pcote=(unsigned long int*)malloc(sizeof(unsigned long int)); forU=O;j<2;j++) H-
>psommet[j]=O;
e=(element)malloc(sizeof ( struct cellule));
for(m=16;m<21 ;m++)
{
M=puissance(m);
I=n*m;
IIp[O]=1 ;for(i=1 ;i<l;i++) p[i]=puissance(i); pfloat[O]=1 ;for(i=1 ;i<l;i++)
pfloat[i]=puissancefloat(i);
c[O]=12; c[1 ]=27;pc=O;surface=(c[O]*c[1]);
*(H->pcote)=M;
for(i=O;i<NMAX;i++)
{
u=O;
forU=O;j<n;j++)
{
a[j]=randO % M;
if( (a [j]+clJ]) >= M )
{
do {a[j]=(9*a[j])/1 O;} while«a[j]+c[j]) >= M); }
f.u[j]=a[j];
f. v[j]=a[j]+c[j];
}
if (pc % 2) {swapi(&(f.u[O]),&(f.u[1]) );swapi(&(f.v[O]),&(f.v[1]) );} pc++;
LTO=creerO;
LTO=eclatement(H);
L=creerO;
L=traitementliste(LTO,f);
nbcp[i]=O;
e=L->prem;
do
if( *(e-> pobj->pstatut)==1)
nbcp[i]+=1 ;
while( (*(e->pobj->pstatut)==1) && (e) )
{e=e->psuiv;}
}
el se if(e) {e=e->psuiv;}
}
while(e);
detruireliste(L);
}
111

---

112
for(i=O;i<NMAX;i++) nb[i+1 ]=nbcp[i];
shellsort(nb, NMAX);umax=nb[NMAX] ;umin=nb[1];
for(i=O;i<NMAX;i++)
{
u+=nbcp[i];
}
uu=(float)u/NMAX;uv=(float)suriace/uu;
fprintf(fic,"%d
%2d
%21u
%f
%21u
%f \\n",n,m,umin,uu,umax,uv
);
}
fclose(fic) ;
}
112

---

BIBLIOGRAPHIE
Aleph-o[1971]:Space-filling curves or how to waste time with a
piotter?
Software-practice and experience
vol 1,403-410 (1971)
Alexandrov,Alexeev & Gorsky[1982]: A recursive algorithm for
pattern recognition
Ch 1801-0/82/0000/0431
1982 IEEE
Alexandrov, Polyakov & Latchinov[1978]: On the recursive
algorithmization of the curve filling up a multidimensional
interval.
Tech.Cybern. n01, 1978
Bartholdi & Platzman[1982] :An (N log N) planar travelling salesman
heuristic based on spacefulling curves
Operations research letters vol 1, n04 sept 1982
Bayer-Mc Creight[1972]:Organisation and maintenance of large
ordered indexes.
Acta informatica 1, 3 (1972), pp 173,189
Bially[1969]: Space-filling curves:their generation and their
application to bandwidth reduction.
I.E.E.E Transactions on information theory
vol 16-15,no6,nov
1969
Butz[1968]: Space-filling curves and mathematical programming.
Information and Control 12, 314-330 (1968)
Butz[1969]:Convergence with Hilbert's space filling curve.
Journal of computer and System Sciences(3) 128-146(1969)
Butz[1971]: Alternative algorithm for Hilbert's space-filling curve.
I.E.E.E Trans.Computer vol C-20 April 1971
Cole[1983]: A note on space-filling curves.
Software-practice and experience,
vo113, 1181-89 (1983)
Diday:Cours polycopié
Ernvall[1984] :On the construction of spanning paths by Gray-code in
compression of files
Technique et science informatiques 3(6) (1984) 411-414
Fagin & all[1979]:Extendible hashing - A fast access method for
dynamic files

---

114
ACM TODS, vol. 4, n°. 3, pp. 315- 344, Sept. 1979
Faloutsos[1986]: Multiattribute Hashing using Gray codes.
SYGMOD 1986 ACM 0-89791-191-1/86/0500/0227
Faloutsos[1987]: Gray codes for partial match and range queries
IEEE trans. on Software Engineering 1987
Faloutsos[1989]:Fractals for secondary key retrieval.
Proc.of the A.C.M on the Principles of Database syst. Mars 1989,
247-252
Faloutsos[1990]:Spatial access methods using Fractals:algorithm
and perfomance evaluation.
Rapport technique Univ.Maryland
Fisher[1986]:A new algorithm for generating Hilbert curves.
Software-practice and experience vol 16 (1 )Uan.1986)
Goldsch lager[1981]: Short algorithms for space-filling curves.
Software-practice and experience, vol 11,99-100 (1981)
Gray[1957]:Pulse code ommunications, U.S Patent 2632058, March
17, 1953
Griffiths[1985]: Table-driven algorithms for generating space-filling
curves.
Computed Aided Design 17(1) 37-41(1985)
Griffiths[1986]:A algorithm for displaying a class of space-filling
curves.
Software-practice and experience
vol 16 (5) 403-411 (may 1986)
Hinrichs & Nievergelt[1983] :The Grid File:a data structure to
support proximity queries on
spatial objects
proc. of the WG'83 (Intern. Workshop on Graph theoretic Concepts
in
Computer Science ), pp 100-113, trauner verlag, Linz, austria,
1983.
Hilbert[1891] : Ueber Stetege Abbildumg einer linie auf ein
Flashentruck 1981 pp 403
Math .Annalen(38) 457-460 (1891)
Kanal & all[1965]: Classification of binary random patterns.
I.E.E.E Transactions on information theory
vol IT·11 ,no4 Oct
1965
Kinderink & Van Doorn[1969]: New type of raster scan preserves the
topology of the image.
114

---

115
Proc.I.E.E.E,vol 67 ,n01 0,1969
Knuth[1973]:The art of Computer Programming, vol 3 Sorting and
searching,
Addison-Wesley, Reading, MA (1973)
Larson[1978]:Dynamic hashing.
BIT, 18, 1978, 184-201
Laurini[1985]:Graphical databases built on Peano space-filling
curves.
Eurographics 1985 Elsevier Sciences Publishers(North-Holland)
Litwin[19805]:a new tool for file and table adressing
Proc. of the sixth Int'I Conf. on Very Large Databases, Montreal,
1980, 212-223
Mandelbrot[1975]: "Les objets fractals"
Nouvelle bibliothèque scientifique Flammarion 1975 pp.40-41
Mandelbrot[1977]:"Fractals,form,chance and dimension."
W.H.Freeman and CO,San-Francisco 1977
Moore[1900]: On certain crinkly curves
Transactions of the American Mathematical Society
vol. 1 pp 72-
90 (1900)
Morrison[1982]:Low cost computer graphics for microcomputer.
Software-practice and experience,
voI19,767-76 (1982)
Orenstein & Merett[1984]:A class of data structures for associative
searching.
1984 ACM 0-89791-128-8/84/004/0181 3
Orenstein[1986]: Spatial query processing in object-oriented
data base system.
1986 ACM 0-89791-191-1/86/0500/0326
Orenstein & Manola[1988]: PROBE spatial data modeling and query
processing in an
image database application.
I.E.E.E Trans.on Softw. Eng. vol 14,n05 May 1988
Palmer[1986]: A Fortran procedure for generating space-filling
curves.
Software-practice and experience vol 16(6) 539-574 Qune 1986)
Patrick & all[1968]: Mapping multidimensional space to one
dimension for computer output display.
I.E.E.E Transactions on computers
vol C-H nOlO oct 1968
Peano[1890] : Sur une courbe qui remplit toute une aire plaine.
115

---

116
Math.Annalen(36) 157-160 (1890)
Richards[1986] :Data compression and Gray-code sorting
Information processing letters
22(1986) 201-205
17 april 1986
Quinquéton & Berthod[1981]: A locally adaptative Peano scanning
algorithm.
I.E.E.E Trans.on Pattern Analysis &Mach.lntelligence, vol
PAMI-3,no4 ,july 1981 pp 403
Samet[1988]: Hierarchical representations of collections of small
rectangles
ACM computing Surveys, 20(4), December 1988,271-309
Sierpinski[1912]: Sur une nouvelle courbe continue qui remplit tout
une aire plane.
BuII.Acad.Sci.Cracovie.Série A 462-478 (1912)
Simon & Quiquéton[1978]: Une méthode de classification basée sur
un balayage
multidimensionnel de Peano.
Bull.Acad.Sciences France vol 286 pp 655
1978
Simon[1984]: Reconnaissance des formes par algorithmes.
Masson Paris 1984
Stevens & Lehar[1978]: Peano curve scanning for automatic shape
detection.
1978,non publié,cité dans Ref. 31
Stevens. Lehar & Preston[1983]: Manipulation and presentation of
multidimensional image data using the Peano scan
IEEE Pattern Analysis and Machine Intelligence, vol. PAMI-5, sept
1983
Witten & Wyvill[1983]: On the generation and the use of space-filling
curves.
Software-practice and experience
vol13 , 519-25 (1983)
Yagadish[1990]: Linear c1ustering of objects with multiple attributes.
1990 ACM 089791-365--5/9010005/6332-51-50
116

---

Vu: le Président
Vu: les suffragants
M
..
MM
.
Vu et permis d'imprimer
Le Vice-président du Conseil Scientifique chargé de la Recherche de
l'Université PARIS-DAUPHINE

---

1
RESUME: les courbes de Peano-Hilbert sont des bijections continues
de Rn dans R. Leurs applications réciproques dites balayages sont
continues presque-partout. D'où l'intérêt de leur utilisation pour le
regroupement des objets dans les bases de données spatiales ou
multidimensionnelles.
Nous introduisons la courbe de Peano pour la comparer à celles qui ont
été jusqu'ici étudiées, c'est-à-dire celle de Hilbert et celle dite z-ordre. En
dimension 2 (seul cas à être étudié jusqu'à présent) les performances des
courbes sont à peu près égales. Mais dès que la dimension des données
devient supérieure à 3, la courbe de Peano devient la plus efficace. Ce
résultat est prouvé analytiquement et est confirmé par les calculs
expérimentaux effectués. Auparavant, nous donnons une méthode générale
de génération des courbes de Peano-Hilbert à partir de celle de Gray.
TITLE:Using Peano-Hilbert curves for objects management in spatial
data bases.
ABSTRACT:Peano-Hilbert curves are continuous and one-to-one
applications from Rn to R. Their reciprocal applications called scannings
are almost-everywhere continuous. That is the reason why they are used for
the clustering of objects in spatial data bases. We introduce the Peano curve
and compare it with Hilbert and
z-order curves.
ln dimension 2, which is the only case studied in the Iitterature, the
performances of curves are almost equal. But when the dimension of data
is greater than 3, the Peano curve becomes more efficient. This result is
proved analytically and confirmed by experiments.
MOTS-CLES: bases de données, données spatiales, objet,
regroupement, cluster, requête par intervalles.

---

RESUME: les courbes de Peano-Hilbert sont des bijections continues
de Rn dans R. Leurs applications réciproques dites balayages sont
continues presque-partout. D'où l'intérêt de leur utilisation pour le
regroupement des objets dans les bases de données spatiales ou
multidimensionnelles.
Nous introduisons la courbe de Peano pour la comparer à celles qui ont
été jusqu'ici étudiées, c'est-à-dire celle de Hilbert et celle dite z-ordre. En
dimension 2 (seul cas à être étudié jusqu'à présent) les performances des
courbes sont à peu près égales. Mais dès que la dimension des dcnnées
devient supérieure à 3, la courbe de Peano devient la plus efficace. Ce
résultat est prouvé analytiquement et est confirmé par les calculs
expérimentaux effectués. Auparavant, nous donnons une méthode générale
de génération des courbes de Peano-Hilbert à partir de celle de Gray.
T1TLE:Using Peano-Hilbert curves fQr abjects management in spatial
databases.
ABSTRACT:Peano-Hilbert curves are continuous and one-ta-one
applications from Rn to R. Their reciprocal applications called scannings
are almost-everywhere continuous. That is the reason why they are used for
the clustering of objects in spatial databases. We introduce the Peano curve
..
and compare it with Hilbert and
z-order curves.
ln dimension 2, which is the only case studied in the Iitterature, the
performances of curves are almost equal. But when the dimension of data
is greater than 3, the Peano curve becomes more efficient. This result is
proved analytically and confirmed by experiments.
MOTS-CLES: bases de données, données spatiales, objet,
regroupement, cluster, requête par intervalles.

---