Structure de données multidimensionnelles

Une structure de données multidimensionnelles est une structure logique permettant de stocker des couples de données afin de leur appliquer des traitements simplifiés.

Ce type de structure est utilisé dans des applications, telles que la géolocalisation, afin de stocker les positions comme un couple de données (Latitude/Longitude/Altitude).

Famille R-Tree

R-Tree^[1]

Le R-Tree est un arbre équilibré, les feuilles de l'arbre contiennent un tableau indexé constitué des références vers les objets stockés. Tous les objets sont stockés dans une collection, chaque objet (ou tuple) possède un identifiant unique afin de pouvoir l'obtenir.

Structure

Les nœuds de l'arbre sont constitués d’éléments de la forme suivante :

${\displaystyle (I,fils-reference)}$

• ${\displaystyle fils-reference}$ : l'adresse du nœud suivant.
• ${\displaystyle I}$ : un rectangle à n dimension contenant tous les rectangles de ces fils.

Les feuilles de l'arbre sont constituées d’éléments de la forme suivante :

${\textstyle (I,tuple-identifiant)}$

• ${\displaystyle tuple-identifiant}$ : un identifiant de tuple.
• ${\displaystyle I}$ : un rectangle à n dimension contenant les objets référencés par cette feuille.

Propriétés

Chaque rectangle représenté par ${\displaystyle I}$ est de la forme : ${\textstyle I=(I_{0},I_{1},...,I_{n-1})}$, avec ${\displaystyle _{n}}$ le nombre de dimension.

En prenant le postulat suivant :

• ${\displaystyle N}$, le nombre d'éléments stockés.
• ${\displaystyle M}$, le nombre maximum d'éléments dans un nœud.
• ${\displaystyle m}$, le nombre minimum d'éléments dans un nœud.

• 

  ${\displaystyle m\leq {M \over 2}}$ , un paramétrage du R-Tree.

L'arbre possède les propriétés suivantes :

• Chaque nœud contient entre ${\displaystyle m}$ et ${\displaystyle M}$ éléments, sauf la racine.
• La racine contient au minimum deux fils sauf si la hauteur de l'arbre est de 0.
• Toutes les feuilles ont une profondeur égale.
• ${\displaystyle \forall (I,fils-reference)\Rightarrow }$ ${\displaystyle I}$ est le plus petit rectangle contenant les rectangles fils.
• ${\displaystyle \forall (I,tuple-identifiant)\Rightarrow }$ ${\displaystyle I}$ est le plus petit rectangle contenant les éléments référencés par la feuille.
• ${\displaystyle h\leq |log_{m}N-1|}$, avec ${\displaystyle h}$ la hauteur de l'arbre.
• ${\displaystyle 1+\sum _{i=1}^{n}\left|{N \over m^{i}}\right|}$, le nombre maximum de nœud.

Hilbert R-Tree^[2]

Cette structure est essentiellement la même que celle du R-Tree, seulement les nœuds sont triés par valeur d'Hilbert afin d'améliorer l'insertion, et par conséquent, obtenir de meilleur résultat que sur le R-Tree.

Nœuds

Chaque nœuds possède une valeur supplémentaire, appelé valeur d'Hilbert maximale. Cette valeur correspond à la valeur d'Hilbert maximale présente parmi tous ces fils.

Cette valeur d'Hilbert est calculée à l'aide de la Courbe d'Hilbert. La valeur d'Hilbert d'un rectangle, est la valeur d'Hilbert du centre du rectangle.

Scission

Dans le R-Tree, il faut attendre ${\displaystyle M+1}$ éléments avant de scinder un rectangle en deux sous-rectangles.

Le Hilbert R-Tree attend que le nœud possède ${\displaystyle M}$ éléments, et son père aussi avant de le scinder.

X-Tree^[3]

Cette structure a pour but d'améliorer la recherche du R-Tree, en effet la recherche dans le R-Tree se détériore très vite lorsque le nombre de dimensions augmente. Cependant, dans le pire des cas, la performance reste similaire au R-Tree.

Son but est de réduire la surface totale couverte par plusieurs rectangles du même nœud (pour une dimension 2).

C'est dans ce but que le X-Tree différencie ces nœuds en deux catégories

• Les nœuds classiques, similaires au R-Tree
• Les super-nœuds.

Super-nœuds

Ces super-nœuds sont semblables aux nœuds classiques d'un R-Tree, cependant la différence se situe sur le nombre maximal d'éléments pouvant être contenus. Ce nombre ${\displaystyle M}$ est supérieur à celui des nœuds classiques.

Leur but est d'éviter la scission le plus possible, afin de réduire les chemins possibles dans l'arbre, et donc d'améliorer le temps de recherche.

Les super-nœuds sont créés à l'insertion lorsque la scission est inévitable.

Famille Kd-Tree

Kd-Tree^[4]

Le kd-tree est un arbre binaire de recherche multidimensionnel où k représente la dimension de l'espace.

Structure

• 

  Chaque nœud contient ${\displaystyle i}$ clés que nous nommerons ${\displaystyle K_{0}(P),...,K_{i}(P)}$.
• Chaque nœud contient deux pointeurs, qui soit sont nuls, soit pointent chacun vers un autre nœud de l'arbre.
• Pour un nœud ${\displaystyle P}$ , nous appellerons ${\displaystyle filsG(P)}$ et ${\displaystyle filsD(P)}$ ses deux pointeurs et ${\displaystyle DISC(P)}$ son discriminant.
• Le discriminant commence à 0 pour le nœud à la racine.
• Pour un nœud ${\displaystyle P}$ ayant pour discriminant ${\displaystyle i}$, ses deux fils ${\displaystyle filsG(P)}$ et ${\displaystyle filsD(P)}$ ont pour discriminant ${\displaystyle DISCSuiv(i)=(i+1)}$ ${\displaystyle mod}$ ${\displaystyle k}$.

Propriétés

• Pour tout ${\displaystyle P}$ dans un kd-tree, soit ${\displaystyle j=DISC(P)}$, alors pour n'importe quel nœud ${\displaystyle Q}$ ${\displaystyle filsG(P)}$, ${\displaystyle K_{j}(Q)<K_{j}(P)}$
• Pour tout ${\displaystyle P}$ dans un kd-tree, soit ${\displaystyle j=DISC(P)}$, alors pour n'importe quel nœud ${\displaystyle Q}$ ${\displaystyle filsD(P)}$, ${\displaystyle K_{j}(Q)>K_{j}(P)}$

KDB-Tree^[5]

Le KDB-tree est une solution pour stocker des enregistrements à clés multiples de grande taille. Pour cela, il s'appuie sur les forces du B-tree ainsi que sur celles du kd-tree afin de proposer un coût en entrée / sortie proche du premier lors de l'ajout ou de la suppression de données, ainsi qu'une performance de recherche proche du second.

Les enregistrements dans un KDB-tree sont de la forme ${\displaystyle cle_{0},cle_{1},...,cle_{k}-_{1}}$ où ${\displaystyle cle_{i}}$ est un élément du ${\displaystyle domaine_{i}}$ et ${\displaystyle k}$ est une constante.

Tout comme pour le B-tree, chaque nœud est stocké comme une page. Nous distinguerons deux types de pages :

un point se décrit comme un élément du domaine ${\displaystyle domaine_{0},domaine_{1},...,domaine_{k}-_{1}}$

une région correspond quant à elle à l'ensemble de tous les points ${\displaystyle x_{0},x_{1},...,x_{k}-_{1}}$ correspondant à ${\displaystyle min_{i}\leq x_{i}<max_{i}}$ , ${\displaystyle 0\leq i\leq k-1}$.

Propriétés

1. Les pages dites régions pointent toujours vers des pages fils et ne peuvent pas être vides. Les pages dites points sont les feuilles de l'arbre.
2. Comme le B tree, la taille du chemin de la racine jusqu'à n'importe quelle feuille est le même.
3. Pour chaque page dite région, les régions dans cette page sont disjointes, et leur union est une région.
4. Si la racine est une région, l'union de ses régions est alors ${\displaystyle domaine_{0},domaine_{1},...,domaine_{k}-_{1}}$ , soit l'espace de recherche entier.
5. Quand le fils d'une paire (région, fils) dans une page dite région est aussi une page région, l'union de toutes les régions du fils est une région.
6. À l'inverse, si la page fils est un point, alors tous les points de la page doivent être dans la région.

BKD-Tree^[6]

Parmi les nombreuses structures de données multidimensionnelles, la performance a tendance à baisser plus le nombre d'ajouts et de suppressions est élevé. En effet, il est compliqué de maintenir les trois caractéristiques suivantes simultanément :

• Un remplissage maximum de la structure
• Un changement minimal de la structure lors de l'ajout ou de la suppression de données.
• Un temps de recherche minimal pour un élément ou une zone de la structure.

L'ajout d'un nœud dans un kd-tree se fait en moyenne en ${\displaystyle O(log\ n)}$, mais ne garde pas une structure équilibrée. En pratique, lors d'un grand nombre d'ajouts, nous sommes donc face à une structure déséquilibrée, ce qui impacte sur la performance des requêtes. De plus, contrairement à certaines structures qui se rééquilibrent facilement pour un coût minimum, celle-ci nécessite le remaniement de larges zones, ce qui diminue fortement ses performances.

De la même manière, le KDB-tree demande potentiellement un large remaniement lors de l'ajout ou de la suppression d'une valeur dans l'arbre, ce qui nuit fortement aux performances de la structure au fur et à mesure que celle-ci se remplit.

Le BKD-tree propose une structure basée sur le KDB-tree qui permet une utilisation de la structure proche de 100% ainsi qu'une excellente performance d'ajout et de suppression comparable à celle du kd-tree. Cependant, contrairement à ce dernier, ces performances sont conservées, peu importe le nombre de requêtes effectuées.

Pour cela, au lieu de construire un seul arbre et de le rééquilibrer après chaque ajout ou suppression de données, il représente chaque sous-arbre comme un kd-tree, et détermine ainsi le strict minimum à rééquilibrer lors de mise à jour de la structure.

Famille Quad-Tree

Quad-Tree^[7]

Le Quad-Tree permet de diviser récursivement l'espace en ${\displaystyle 2^{n}}$ parties. Le Quad-Tree est utilisé pour un espace à 2 dimensions, cependant le concept peut s’étendre à ${\displaystyle n}$ dimensions.

Structure

Les nœuds de l'arbre sont de la structure suivante :

${\displaystyle (I,elements)}$

• ${\displaystyle I}$ , l'espace couvert par le nœud en question.
• ${\displaystyle elements}$, l'ensemble des éléments couverts par ce nœud.

Propriétés

En prenant le postulat suivant :

• ${\displaystyle M}$, le nombre maximal d'éléments dans un nœud.
• ${\displaystyle n}$, le nombre de dimensions.
• ${\displaystyle S}$, la surface totale couverte par l'arbre
• ${\displaystyle p}$, la profondeur d'un nœud.

L'arbre possède les propriétés suivantes :

• Si un nœud possède ${\displaystyle M+1}$ éléments, alors ces derniers sont repartis dans ${\displaystyle 2^{n}}$ fils, chacun représentant une fraction égale de l'espace couvert par ${\displaystyle I}$.
• Un nœud de profondeur ${\displaystyle p}$ couvre ${\displaystyle 1 \over p2^{n}}$ de S

Famille Patricia-Tree

Patricia-Tree^[8]

Le terme "Patricia" signifie "Practical Algorithm To Retrieve Information Coded In Alphanumeric".

Le Patricia-Tree permet de stocker des chaines de caractères de manière optimisée, en matière de performances, et d'espace.

Ce type d'arbre est souvent utilisé pour la prédiction de mot contenu dans un dictionnaire.

Structure

Les nœuds de l'arbre sont de la structure suivante :

${\displaystyle (C)}$

• Une chaîne de caractère.

Propriétés

En prenant le postulat suivant :

• ${\displaystyle S_{max}}$, la taille du mot le plus long stocké dans l'arbre.
• La racine correspond à la chaîne vide.

L'arbre possède les propriétés suivantes :

• Tous les fils d'un nœud correspondent à des mots ayant un préfixe commun.
• Plus les mots stockés dans l'arbre possèdent des préfixes, plus l'espace mémoire est optimisé.
• La profondeur de l'arbre est égale à ${\displaystyle S_{max}}$

Famille PH-Tree

PH-Tree^[9]

Le PH-Tree reprend deux concepts, ceux de la famille des Patricia-Tree, ainsi que ceux du Quad-Tree (Hypercube, lorsqu'on étend le concept à ${\displaystyle n}$ dimensions).

Cet arbre, à la différence des Patricia-Tree, ne se contente pas de stocker des chaines de caractères, il permet de stocker des objets complexes, par exemple des tuples de ${\displaystyle n}$ entiers.

Pour ce faire, le PH-Tree stocke des bits à la place des caractères.

Structure

Les nœuds de l'arbre sont de la structure suivante :

${\displaystyle (Prefixe,HC,Postfixes)}$

• ${\displaystyle Prefixe}$, les ${\displaystyle n}$ premiers bits partagés.
• ${\displaystyle HC}$, un tableau de ${\displaystyle 2^{n}}$ cases, contenant chacune ${\displaystyle n}$ bits.
• ${\displaystyle Postfixes}$, un tableau de ${\displaystyle 2^{n}}$ cases, contenant chacune ${\displaystyle n}$ bits, représente la fin de la représentation binaire de l'objet stocké.

La racine de l'arbre est de la structure suivante :

${\displaystyle (HC)}$

• ${\displaystyle HC}$, un tableau de ${\displaystyle 2^{n}}$ cases, contenant chacune ${\displaystyle n}$ bits.

Propriétés

En prenant le postulat suivant :

• ${\displaystyle S_{max}}$, la taille de la représentation binaire la plus longue stockée.
• On peut interpréter la racine comme l'objet ${\displaystyle null}$

L'arbre possède les propriétés suivantes :

• Tous les fils d'un nœud possèdent le même début de représentation binaire pour chaque dimension.
• Plus les objets stockés dans l'arbre possèdent des représentations binaires communes, plus l'espace mémoire est optimisé.
• La profondeur de l'arbre est égale à ${\displaystyle S_{max}}$

Comparatif

Le tableau ci-dessous reprend une liste non exhaustive des complexités des différentes opérations appliquées aux structures décrites.

		Complexité
		Insertion	Modification	Suppression	Recherche
Tree	R	${\displaystyle \Theta (n)}$	${\displaystyle \Theta (n*log(n))}$	${\displaystyle \Theta (n)}$	${\displaystyle \Theta (log(m^{n}))}$
	Hilbert				${\displaystyle \Theta (log(m^{n}))}$
	X	${\displaystyle \Theta (n*log(n))}$		${\displaystyle \Theta (n)}$	${\displaystyle \Theta (log(m^{n}))}$
	KD	${\displaystyle \Theta (n)}$	${\displaystyle \Theta (n)}$	${\displaystyle \Theta (n)}$	${\displaystyle \Theta (n)}$
	BKD
	KDB
	Quad	${\displaystyle \Theta (log(n))}$			${\displaystyle \Theta (log(n))}$
	Patricia	${\displaystyle \Theta (S_{max})}$	${\displaystyle \Theta (S_{max})}$	${\displaystyle \Theta (S_{max})}$	${\displaystyle \Theta (S_{max})}$
	PH	${\displaystyle \Theta (log(n_{max}))}$	${\displaystyle \Theta (log(n_{max}))}$	${\displaystyle \Theta (log(n_{max}))}$	${\displaystyle \Theta (log(n))}$

Références

• Portail de l’informatique
• Portail de la programmation informatique