Brevet FR2856494A1 — publié le 20041224

PROCEDE D'INDEXATION SPATIALE La présente invention se rapporte au domaine de l'indexation spatiale. La présente invention se rapporte plus particulièrement à un procédé d'indexation spatiale d'objets géométrique par décomposition arborescente d'un domaine. L'art antérieur connaît déjà, par le brevet américain US 6 161 105 (Oracle), un procédé et un appareil pour les bases de données multidimensionnelles utilisant du code binaire hyperspatial. Ce document présente une structure et un type de données visant à améliorer le stockage et la 15 manipulation de données spatiales multidimensionelles dans une base de données ainsi que l'accès à ces données. Un code binaire hélicoïdal hyperspatial (CODE HH) est employé afin de représenter des données de N dimensions, la structure de données de type CODE HH binaire maintenant 20 l'organisation dimensionnelle de données multidimensionnelles à l'intérieur même de ces données. Les données spatiales sont stockées grâce à un code BH (code binaire hyperspatial) qui est conçu comme un dérivé de structure en arborescence à N niveaux à l'aide de la 25 décomposition par récurrence. Une zone physiquement neutralisée définit la limite maximale du volume de données pouvant être stockées dans une partition quelle qu'elle soit. Dès que le volume des données stockées dans une partition dépasse la limite fixée par la zone physiquement 30 neutralisée, les données sont décomposées en partitions filles de manière à ce qu'aucun stockage de données en partitions ne dépasse ladite limite. Si la limite fixée par la zone physiquement neutralisée est dépassée, des partitions filles supplémentaires sont automatiquement générées et le tableau mère n'est plus conservé. Cette invention concerne également une structure de données représentant les tableaux découpés et les valeurs de code 5 BH. Des attributs pertinents sont associés à chacune des valeurs de code BH, ces attributs pouvant représenter des données non spatiales telles que la température, la salinité ou le flux de rayonnement cosmique. Cette invention prévoit également une méthode et un appareil pour 10 l'application aux segments de lignes et à la topologie des avantages que présente le code HH binaire. L'art antérieur connaît également, par le brevet américain US 5 963 956 (Telcontar), un système et un procédé pour optimiser les requêtes de bases de données en 15 deux dimensions ou plus. L'invention de ce document concerne un procédé et un système de stockage et de récupération d'objets de données spatiales dans une base de données spatiales. Le système stocke des objets multidimensionnels à l'intérieur de la base de données en 20 déterminant leur position dans un système de coordonnées multiniveau. A chaque objet est attribuée une coordonnée particulière et l'objet est affecté à une section de plusieurs sections se chevauchant à l'intérieur du système de coordonnées. Chaque objet est affecté à une section 25 particulière du système de coordonnées en fonction de sa taille et de sa position globale. Il est également proposé, par la demande de brevet PCT WO 02/073459 (Opteway), un procédé pour rechercher un objet dans un domaine d au sein d'un espace D contenant un 30 ensemble d'objets décrits dans une matrice M initiale, comprenant une construction d'un sous-ensemble w d'objets contenus dans ledit domaine d par extraction d'une matrice m à partir de la matrice M initiale. Un matriçage M de l'espace D est créé en superposant une pluralité de matrices géométriques de normes r différentes, chacune des mailles de chaque matrice géométrique étant identifiée par une valeur numérique spécifique et unique appelée code de 5 matrice. On trie la matrice M par codes de matrice selon un ordre prédéterminé, des normes r. Puis, on construit la matrice d'extraction m décrivant les seuls objets concernés par lesdites mailles incluses dans le domaine d ou intersectées par le domaine d. 10 Etant donné un ensemble indexé E de n objets géométriques inclus dans un domaine D, le problème que la présente invention se propose de résoudre est le suivant: Comment extraire de D les objets de E qui 15 intersectent un sous domaine D' de D (D' c D) ? La solution naïve consiste à parcourir tous les objets de E et de vérifier pour chacun s'il y a intersection avec D'. Le nombre d'opérations élémentaires à 20 effectuer est indépendant de D' : que D' soit égal à D ou que D' soit beaucoup plus petit que D, le nombre d'opérations élémentaires à effectuer est identique. On se propose de présenter ici une solution qui est 25 d'autant plus rapide que D' est petit par rapport à D. La solution repose sur un système d'indexation spatiale des objets de E de sorte que le rang d'un objet dans E constitue une indication sur la position dans 30 l'espace de cet objet. La solution consiste à définir préalablement un recouvrement SD de sous domaines de D et de classer les objets de E en fonction de leur " appartenance " à ces sous-domaines. A chaque sous-domaine est associé l'index du premier objet de E qui lui est associé. Ainsi, étant donné D', une première étape consiste à déterminer quels sont les sous domaines de SD qui intersectent D' puis, de ne traiter que les objets associés 5 à ces sous domaines. Le traitement des objets restant consiste alors à vérifier s'ils intersectent ou non D'r. La première étape est a priori très rapide dans la mesure o le cardinal de SD est beaucoup plus petit que le cardinal de E. La rapidité de la deuxième étape dépend du 10 nombre de sous domaines de SD qui auront été éliminés dans la première étape: plus D' est petit, plus il y aura eu de sous domaines éliminés, plus petit sera le nombre d'objets à traiter. Cette approche pose cependant un problème non trivial: Comment établir une relation d'inclusion entre un objet géométrique et un sous domaine ? 20 Si l'objet est un point, le problème est trivial: un point est soit inclus dans un domaine soit extérieur à ce domaine. Dans le cas contraire, se pose le problème d'un objet intersectant un domaine sans être inclus dans ce 25 domaine. SD étant un recouvrement de D, il y a forcément au moins un autre élément de SD qui intersecte un tel objet. C'est le problème du chevauchement. Avec quel élément de SD faut-il alors associer cet objet ? Les systèmes existants basées sur une technique d'indexation spatiale se décomposent en deux familles, chacune d'entreselles apportant une solution différente au problème précédent: 1. Solutions basées sur un recouvrement strict: SD est un recouvrement strict de D (i.e. pas 5 d'intersection entre les éléments de SD). Les objets géométriques qui chevauchent plusieurs éléments de SD sont " découpés " en sous objets de manière à ce que ces sous objets ne chevauchent pas les éléments de SD. Le découpage d'objets permet donc de résoudre le problème du 10 chevauchement mais il complique sensiblement les problèmes de codage des objets et il accroît le nombre d'octets nécessaires à leurs codages. De plus, le découpage d'objets accroît le nombre d'éléments géométriques. 2. Solutions basées sur un recouvrement hiérarchique: Les éléments de SD sont hiérarchisés en fonction de leur taille. Le plus grand élément est égal à D lui-même ce 20 qui permet de garantir que chaque objet de E est inclus dans au moins un élément de SD (car, par définition, D contient tous les objets géométriques de E). Les éléments de SD sont classés en différents niveaux. Chaque niveau constitue un recouvrement strict de D et correspond à une 25 taille donnée. Cette approche évite ainsi de devoir décomposer les objets en sous objets. En revanche, l'efficacité de cette approche dépend du nombre d'objets qui seront associés aux plus petits éléments de SD. En effet les " petits " éléments de SD sont plus facilement 30 " éliminables " lors de la première phase de l'algorithme que les " gros ". Le plus gros, qui est égal à D n'est, lui, jamais éliminé. Or, si relativement beaucoup d'objets sont associés aux gros éléments de SD, peu d'objets sont susceptibles d'être éliminés dans la première phase. L'association des objets avec les sous domaines se fait de la façon suivante: En fonction de la taille de l'objet (ou l'encombrement) un niveau est sélectionné (le niveau o les sous domaines ont une taille suffisante pour contenir l'objet. Si l'objet chevauche les sous domaines de ce niveau, on réitère l'opération au niveau immédiatement 10 inférieur (o les sous domaines sont plus grands) tant qu'il y a chevauchement (éventuellement, jusqu'au niveau 0 o ne figure qu'un seul sous domaine égal à D). Le procédé qui consiste à descendre de niveau lors de l'attribution d'un sous domaine à un objet sera appelé " processus de 15 dégradation ". La présente invention entend remédier aux inconvénients de l'art antérieur en proposant une solution d'indexation spatiale qui contourne les inconvénients des 20 deux méthodes précédentes: découpage des objets et processus de dégradation. A cet effet, l'invention concerne, dans son acception la plus générale, un procédé d'indexation spatiale d'un 25 ensemble E d'objets géométriques appartenant à un domaine D borné de dimension n, n étant un entier naturel, comprenant les étapes suivantes: * Définir un indexage des noeuds d'un arbre A de 30 profondeur p, chaque niveau dudit arbre étant associé à un recouvrement du domaine D et chaque noeud dudit arbre comportant des fils constituant un recouvrement de ce noeud et étant associé à un élément du recouvrement correspondant à la profondeur de ce noeud; * Associer à chaque objet géométrique 0 de E un index d'un noeud dudit arbre; o Cette étape d'association comportant les deux sous-étapes suivantes: a Définir la profondeur P(O) de l'arbre à laquelle l'objet géométrique 0 est associé ; a Définir le noeud N(O) ayant la profondeur P(O) auquel l'objet géométrique 0 est associé ; * Construire un sous-arbre SA(A) de l'arbre A, ce sous-arbre étant construit de façon itérative à partir de A 15 en supprimant des noeuds feuilles: a chaque itération, les noeuds feuilles auxquels moins de nMin objets de E ont été associés à l'étape précédente sont supprimés, les objets des noeuds feuilles, lorsqu'il y en a, sont alors associés au noeud père du noeud supprimé ; 20 caractérisé en ce que la définition de la profondeur P(O) à laquelle l'objet géométrique 0 est associé consiste en la définition du rectangle circonscrit à l'objet géométrique et en la recherche de la profondeur maximale à 25 laquelle ce rectangle circonscrit est susceptible, indépendamment de la position de l'objet, d'être inclus dans un des noeuds ce cette profondeur (il est supposé ici que les domaines sont rectangulaires et donc que la " possibilité d'inclusion " est la même pour tous les noeuds 30 d'une profondeur donnée) ; et en ce que la définition du noeud N(O) auquel l'objet géométrique 0 est associé consiste en la sélection du noeud tel que l'intersection de son domaine avec le rectangle circonscrit est maximale. De préférence, le domaine D est " rectangulaire " et en ce que chaque noeud possède 2n fils, les 2n sous-domaines correspondant aux fils représentent des partitions par 2 suivant chaque dimension n du domaine correspondant au père. Avantageusement, le procédé d'extraction parcourt les noeuds par ordre croissant de profondeur de sorte que les objets soient accédés pas ordre décroissant de taille (de manière à gérer correctement les problèmes d'ordre d'affichage) et en ce que le parcours des 15 noeuds utilise une pile de type FIFO (First In First Out) garantissant aussi que les descendants d'un noeud qui n'intersecte pas la zone d'extraction ne soient pas parcourus. Selon un mode de mise en oeuvre particulier, le codage 20 est réalisé de façon binaire. Avantageusement, les algorithmes de construction de l'arbre sont mis en oeuvre de la façon suivante: en fonction de leur taille et de leur position, les objets sont associés aux noeuds d'un arbre complet (arbre tel que 25 chaque noeud a 2n fils) par un système d'indexation des noeuds de cet arbre, les feuilles de l'arbre complet telles que moins de nMin objets de E leur ont été associés sont supprimées, cette dernière étape étant réitérée tant qu'il y a des feuilles de l'arbre complet telles que moins de 30 nMin objets de E leur ont été associés, les objets étant triés au sein de chaque noeud par ordre décroissant de taille. L'invention se rapporte également à un système pour la mise en oeuvre du procédé. Avantageusement, le système est un système d'information géographique. On comprendra mieux l'invention à l'aide de la description, faite ciaprès à titre purement explicatif, d'un mode de réalisation de l'invention, en référence aux figures annexées: À la figure 1 illustre un exemple de décomposition hiérarchique d'un domaine rectangulaire; À la figure 2 représente un sous arbre T dans un mode de réalisation particulier; À la figure 3 illustre un ensemble SD défini par 15 l'arbre T représenté sur la figure 2; * la figure 4 illustre la mise en correspondance d'un objet géométrique avec un noeud; À la figure 5 illustre la zone d'influence associée à un noeud; À la figure 6 illustre l'étape d'extraction des noeuds d'un arbre; a la figure 7 illustre l'étape d'extraction des objets géométriques; * la figure 8 illustre un arbre et une représentation 25 du codage binaire; et * la figure 9 illustre l'association entre les noeuds et les positions des objets. Dans un premier temps, la décomposition arborescente 30 d'un domaine sera décrite. Dans la suite, D sera un domaine discret de dimension 2 et de forme rectangulaire avec 2 côtés horizontaux et 2 côtés verticaux. Soit T un arbre de degré 4 non complet (un noeud a au 5 plus 4 fils). A chaque noeud de T est associé un rectangle. La racine de T est associée à un rectangle r tel que D c r. A chaque noeud est associé un des 4 rectangles définis par les médianes du rectangle associé à son père. Les fils d'un noeud sont ordonnés de sorte que le premier correspond, 10 par exemple, au sous rectangle en haut à gauche, puis en haut à droite, puis en bas à gauche puis en bas à droite. Ainsi, la connaissance de la position d'un noeud dans T définit exactement le rectangle associé et, par extension, la connaissance de T et du rectangle associé à sa racine 15 définit précisément un ensemble SD de rectangles. L'arbre considéré T est représenté sur la Figure 1 et l'ensemble SD de rectangles est illustré Figure 2. Pour chaque niveau p de T, tous les rectangles ont la même dimension définie par la paire (Xp, Yp) o Xp = Xo / 2P et Yp = Yo / 2P. Pour chaque objet géométrique O, on définit un rectangle englobant Ro = (Xomin, Yomin; Xomax, Yomax) o Xomin (respectivement Yomin) vaut la valeur minimale en X 25 (respectivement en Y) de O et Xomax (respectivement Yomax) vaut la valeur maximale en X (respectivement en Y) de O. La mise en correspondance d'un objet O avec un noeud de T s'effectue en deux temps: 30 Détermination du niveau po de T Détermination du noeud no de T au niveau Po. po est déterminé de la façon suivante Po = maxP tel que (Xp Ä Xomax Xomin) et (Yp > Yomax - Yomin) Au niveau po, il est facile de démontrer que Ro intersecte au maximum quatre rectangles des noeuds de ce niveau (si Ro intersecte plus de quatre rectangles, alors Ro est plus grand, en X ou en Y, que les rectangles au 10 niveau po, 0 ne peut donc avoir été placé à ce niveau) no = max nZENpo Surface(Rn n Ro) O R, est le rectangle associé au noeud n et Npo l'ensemble des noeuds au niveau po. La mise en correspondance d'un objet géométrique avec un noeud est illustrée Figure 4. 20 Ainsi, les objets ne sont ni découpés ni dégradés (car seule la taille de l'objet détermine le niveau du noeud auquel il sera associé, pas sa position) . En revanche, l'association d'un objet O à un rectangle Rn ne garantit 25 pas que Ro c Rn mais le domaine délimité par l'ensemble des objets associés à un noeud n donné est un rectangle R'o centré sur Rn et dont les côtés sont deux fois plus longs que ceux de Rn, comme l'illustre la figure 5. En effet, le système d'association des objets 30 géométriques aux noeuds de T est tel que si un objet dépasse les limites de R'n, il ne peut être associé au noeud n. Dans la suite, R'I est appelé zone d'influence du noeud n. La construction de T est telle que les zones d'influences des fils d'un noeud n sont toutes incluses dans 5 la zone d'influence de n et, par transitivité, que les zones d'influences de tous les descendants d'un noeud n sont comprises dans la zone d'influence de n. Considérons l'algorithme d'extraction des objets de 10 E intersectant un sous-domaine D' de D. e Première étape: extraction des noeuds de T. Cette étape consiste à déterminer l'ensemble des 15 noeuds de T qui intersectent le rectangle Re d'extraction (i.e. D' = Re) . Etant donné que les objets ne sont pas nécessairement inclus dans le rectangle du noeud auquel ils sont associés, il convient de vérifier, pour un noeud n, si sa zone d'influence R'o intersecte Re, comme l'illustre la 20 figure 6. La structure arborescente de T permet d'éviter le parcours systématique de tous les noeuds de T. En effet, lorsque la zone d'influence d'un noeud n'intersecte pas le 25 rectangle d'extraction, non seulement celui-ci n'est pas concerné pas l'extraction, mais aussi tous ses descendants. Il n'est donc pas nécessaire de vérifier l'intersection avec ses descendants. Les noeuds de l'arbre sont parcourus par ordre croissant de profondeur (i. e. de la racine vers les feuilles) tous les noeuds d'une profondeur p sont parcourus avant les noeuds de profondeur p+l. Ceci permet de parcourir les objets par ordre décroissant de taille de manière à garantir, lorsqu'il s'agit de dessiner les objets, de gérer correctement l'ordre d'affichage (si l'on dessine un objet petit avant un objet plus grand, le 5 premier objet risquerait d'être caché par le deuxième). Une pile de type FIFO (First In First Out) permet de gérer l'ordre de parcours des noeuds: La pile est initialisée avec le noeud racine. Lorsqu'on accède à un noeud par le biais de la pile, on effectue le test d'intersection pour 10 chacun de ses fils, si le test est positif, le fils est alors ajouté à la pile. Ceci permet de parcourir les noeuds dans l'ordre souhaité et aussi de ne pas parcourir les descendants des noeuds qui ne vérifient pas le test d'intersection avec Re À Deuxième étape extraction des objets géométriques. Cette deuxième étape consiste simplement à vérifier 20 l'intersection des objets des noeuds sélectionnés dans la première étape avec le rectangle d'extraction. Il y a cependant moyen d'optimiser cette étape. En effet, pour les noeuds dont seule la zone d'influence intersecte le rectangle d'extraction, on peut montrer 25 facilement que les objets d'une taille inférieure à un certain seuil ne peuvent intersecter le rectangle d'extraction. Voici comment ce seuil est déterminé On définit la taille size(O) d'un objet O par 30 size(O) = max { (Xomax - Xomin) ; (Yomax - Yomin) } Si n est un noeud tel que Rn n Re = 0 et tel que R'n q Re # 0, on définit dist(Rn, Re) la distance minimale entre Rn et Re. alors, tous les objets O de n tel que: size(O) La figure 7 illustre cette étape. 2 x dist(Rn, Re) définit donc un seuil en deçà duquel, tout objet du noeud n est trop petit pour 15 intersecter Re. Un filtrage préalable sur la taille des objets peut donc permettre d'éliminer certains objets avant le test ultime (plus coûteux) de l'intersection entre les objets restant et le rectangle d'extraction. 20 La présence ou non des fils d'un noeud peut se coder sur quatre bits, chacun correspondant à un des quatre sous rectangles: ler bit: présence ou non d'objets dans le sous rectangle en haut à gauche. 2ème bit: présence ou non d'objets dans le sous rectangle en haut à droite. 3ème bit: présence ou non d'objets dans le sous rectangle en bas à gauche. 4ème bit: présence ou non d'objets dans le sous rectangle en bas à droite. On appelle état d'un noeud le codage de ce noeud. Par exemple, l'état d'une feuille de l'arbre sera toujours 0000, celui d'un noeud avec trois fils sera 0111, 1011, 1101 ou 1110 selon le fils manquant. La topologie de cet arbre se code, dans une table d'états, de la façon suivante: 1111/0101/1011/1110/0100/0000/0000/0000/0000/0000/0000/1001 10 /0000/0000/0000/0000 Cet arbre et le codage sont représentés sur la Figure 8. Les noeuds sont donc ordonnés par ordre croissant de profondeur et de haut en bas (du point de vue de la représentation graphique de l'arbre). La table d'états plus la connaissance du rectangle 20 associé à la racine de T détermine exactement à la fois T et SD. Le nombre de noeuds d'un arbre de degré 4 de profondeur n est inférieur ou égal à (4+1z-1)/3 (somme d'une 25 suite géométrique de raison 4) . Par exemple, un arbre de degré 4 et de profondeur 5 a au plus 1365 noeuds. La topologie de l'arbre, c'est-à-dire l'état de l'ensemble de ses noeuds peut donc se coder sur au plus 1365 / 2 = 683 octets. A la profondeur 5, le domaine est décomposé en 32 x 30 32 rectangles (32 = 25). Les objets de l'ensemble E sont rangés en fonction de leurs noeuds d'attribution. A l'intérieur d'un même noeud, les objets sont rangés par ordre décroissant de taille. A chaque noeud est associé la position du premier objet dans E qui lui est associé, comme l'illustre la figure 9. Lorsque l'on souhaite atteindre les objets 10 intersectant un rectangle d'extraction donné et que l'on arrive sur un noeud dont la zone d'influence n'intersecte pas ce rectangle, alors on passe directement à son frère car tous ses descendants n'intersectent pas non plus le rectangle. L'accès des objets intersectant un rectangle 15 donné est donc très rapide, seuls les objets " utiles " sont vus. Dans le cas d'un noeud dont seule la zone d'influence intersecte le rectangle d'extraction, les objets étant classés par ordre décroissant de taille, on s'arrête dès qu'un objet a une taille inférieure au seuil 20 et on passe au noeud suivant. * Extension du procédé à un espace en n dimensions En n dimensions, T est un arbre de degré 2n: les 25 rectangles deviennent alors des parallélépipèdes de dimension n. Chaque parallélépipède se décompose en 2 n sous parallélépipèdes. Pour le reste, l'extension du procédé en n dimensions est triviale. L'invention est décrite dans ce qui précède à titre d'exemple. Il est entendu que l'homme du métier est à même de réaliser différentes variantes de l'invention sans pour autant sortir du cadre du brevet. REVENDICATIONS 1. Procédé d'indexation spatiale d'un ensemble E d'objets géométriques appartenant à un domaine D borné de 5 dimension n, n étant un entier naturel, comprenant les étapes suivantes: À Définir un indexage des noeuds d'un arbre A de profondeur p, chaque niveau dudit arbre étant associé à un recouvrement du domaine D et chaque noeud dudit arbre 10 comportant des fils constituant un recouvrement de ce noeud et étant associé à un élément du recouvrement correspondant à la profondeur de ce noeud; a Associer à chaque objet géométrique 0 de E un index d'un noeud dudit arbre; o Cette étape d'association comportant les deux sous-étapes suivantes: a Définir la profondeur P(O) de l'arbre à laquelle l'objet géométrique 0 est associé ; À Définir le noeud N(O) ayant la profondeur P(O) auquel l'objet géométrique O est associé ; À Construire un sous-arbre SA(A) de l'arbre A, ce sous-arbre étant construit de façon itérative à partir de A 25 en supprimant des noeuds- feuilles: à chaque itération, les noeuds feuilles auxquels moins de nMin objets de E ont été associés à l'étape précédente sont supprimés, les objets des noeuds feuilles, lorsqu'il y en a, sont alors associés au noeud père du noeud supprimé ; 30 caractérisé en ce que la définition de la profondeur P(O) à laquelle l'objet géométrique 0 est associé consiste en la définition du rectangle circonscrit à l'objet géométrique et en la recherche de la profondeur maximale à laquelle ce rectangle circonscrit est susceptible, indépendamment de la position de l'objet, d'être inclus dans un des noeuds ce cette profondeur (il est supposé ici 5 que les domaines sont rectangulaires et donc que la " possibilité d'inclusion " est la même pour tous les noeuds d'une profondeur donnée); et en ce que la définition du noeud N(O) auquel l'objet géométrique 0 est associé consiste en la sélection 10 du noeud tel que l'intersection de son domaine avec le rectangle circonscrit est maximale. 2. Procédé d'indexation spatiale d'un ensemble E 15 d'objets géométriques selon la revendication 1, caractérisé en ce que le domaine D est " rectangulaire " et en ce que chaque noeud possède 2n fils, les 2n sousdomaines correspondant aux fils représentent des partitions par 2 suivant chaque dimension n du domaine correspondant au 20 père. 3. Procédé d'indexation spatiale d'un ensemble E d'objets géométriques selon la revendication 1 ou 2, caractérisé en ce que le procédé d'extraction parcourt les 25 noeuds par ordre croissant de profondeur de sorte que les objets soient accédés pas ordre décroissant de taille (de manière à gérer correctement les problèmes d'ordre d'affichage) et en ce que le parcours des noeuds utilise une pile de type FIFO (First In First Out) garantissant aussi 30 que les descendants d'un noeud qui n'intersecte pas la zone d'extraction ne soient pas parcourus. 4. Procédé d'indexation spatiale d'un ensemble E d'objets géométriques selon la revendication 1, 2 ou 3, caractérisé en ce que le codage est réalisé de façon binaire. 5. Procédé d'indexation spatiale d'un ensemble E d'objets géométriques selon l'une quelconque des revendications précédentes, caractérisé en ce que les algorithmes de construction de l'arbre sont mis en oeuvre de 10 la façon suivante: en fonction de leur taille et de leur position, les objets sont associés aux noeuds d'un arbre complet (arbre tel que chaque noeud a 2n fils) par un système d'indexation des noeuds de cet arbre, les feuilles de l'arbre complet telles que moins de nMin objets de E 15 leur ont été associés étant supprimées, cette dernière étape étant réitérée tant qu'il y a des feuilles de l'arbre complet telles que moins de nMin objets de E leur ont été associés, et les objets étant triés au sein de chaque noeud par ordre décroissant de taille. 20 6. Système pour la mise en oeuvre du procédé selon l'une quelconque des revendications précédentes. 7. Système selon la revendication 6, caractérisé en 25 ce qu'il est un système d'information géographique.