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 :

$(I,fils-reference)$

$fils-reference$ : l'adresse du nœud suivant.
$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)}$

Représentation d'un R-Tree dans un espace 2 dimensions

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

Propriétés

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

En prenant le postulat suivant :

$N$ , le nombre d'éléments stockés.
$M$ , le nombre maximum d'éléments dans un nœud.
$m$ , le nombre minimum d'éléments dans un nœud.
Une bonne et une mauvaise scission
$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 $m$ et $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.
$\forall (I,fils-reference)\Rightarrow$ $I$ est le plus petit rectangle contenant les rectangles fils.
$\forall (I,tuple-identifiant)\Rightarrow$ $I$ est le plus petit rectangle contenant les éléments référencés par la feuille.
$h\leq |log_{m}N-1|$ , avec $h$ la hauteur de l'arbre.
$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 $M+1$ éléments avant de scinder un rectangle en deux sous-rectangles.

Le Hilbert R-Tree attend que le nœud possède $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 $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

Exemple de 2d-tree
Chaque nœud contient $i$ clés que nous nommerons $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 $P$ , nous appellerons $filsG(P)$ et $filsD(P)$ ses deux pointeurs et $DISC(P)$ son discriminant.
Le discriminant commence à 0 pour le nœud à la racine.
Pour un nœud $P$ ayant pour discriminant $i$ , ses deux fils $filsG(P)$ et $filsD(P)$ ont pour discriminant $DISCSuiv(i)=(i+1)$ $mod$ $k$ .

Propriétés

Pour tout $P$ dans un kd-tree, soit $j=DISC(P)$ , alors pour n'importe quel nœud $Q$ $filsG(P)$ , $K_{j}(Q)<K_{j}(P)$
Pour tout $P$ dans un kd-tree, soit $j=DISC(P)$ , alors pour n'importe quel nœud $Q$ $filsD(P)$ , $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 $cle_{0},cle_{1},...,cle_{k}-_{1}$ où $cle_{i}$ est un élément du $domaine_{i}$ et $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 $domaine_{0},domaine_{1},...,domaine_{k}-_{1}$

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

Propriétés

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.
Comme le B tree, la taille du chemin de la racine jusqu'à n'importe quelle feuille est le même.
Pour chaque page dite région, les régions dans cette page sont disjointes, et leur union est une région.
Si la racine est une région, l'union de ses régions est alors $domaine_{0},domaine_{1},...,domaine_{k}-_{1}$ , soit l'espace de recherche entier.
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.
À 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 $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 affecte 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 $2^{n}$ parties. Le Quad-Tree est utilisé pour un espace à 2 dimensions, cependant le concept peut s’étendre à $n$ dimensions.

Structure

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

$(I,elements)$

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

Propriétés

En prenant le postulat suivant :

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

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

Si un nœud possède $M+1$ éléments, alors ces derniers sont repartis dans $2^{n}$ fils, chacun représentant une fraction égale de l'espace couvert par $I$ .
Un nœud de profondeur $p$ couvre $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 :

$(C)$

Une chaîne de caractère.

Propriétés

En prenant le postulat suivant :

$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 à $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 à $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 $n$ entiers.

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

Structure

Structure interne d'un PH-Tree à 2 dimensions, contenant 3 couples de données.

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

$(Prefixe,HC,Postfixes)$

$Prefixe$ , les $n$ premiers bits partagés.
$HC$ , un tableau de $2^{n}$ cases, contenant chacune $n$ bits.
$Postfixes$ , un tableau de $2^{n}$ cases, contenant chacune $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 :

$(HC)$

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

Propriétés

En prenant le postulat suivant :

$S_{max}$ , la taille de la représentation binaire la plus longue stockée.
On peut interpréter la racine comme l'objet $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 à $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	$\Theta (n)$	$\Theta (n*log(n))$	$\Theta (n)$	$\Theta (log(m^{n}))$
	Hilbert				$\Theta (log(m^{n}))$
	X	$\Theta (n*log(n))$		$\Theta (n)$	$\Theta (log(m^{n}))$
	KD	$\Theta (n)$	$\Theta (n)$	$\Theta (n)$	$\Theta (n)$
	BKD
	KDB
	Quad	$\Theta (log(n))$			$\Theta (log(n))$
	Patricia	$\Theta (S_{max})$	$\Theta (S_{max})$	$\Theta (S_{max})$	$\Theta (S_{max})$
	PH	$\Theta (log(n_{max}))$	$\Theta (log(n_{max}))$	$\Theta (log(n_{max}))$	$\Theta (log(n))$

Références

↑ Antonin Guttman, « R-trees: A Dynamic Index Structure for Spatial Searching », SIGMOD, ACM, sIGMOD '84,‎ 1^er janvier 1984 (ISBN 0-89791-128-8, DOI 10.1145/602259.602266, lire en ligne)
↑ Ibrahim Kamel et Christos Faloutsos, « Hilbert R-tree: An Improved R-tree Using Fractals », VLBD, Morgan Kaufmann Publishers Inc., vLDB '94,‎ 1^er janvier 1994 (ISBN 1-55860-153-8, lire en ligne)
↑ Stefan Berchtold, Daniel A. Keim et Hans-Peter Kriegel, « The X-tree: An Index Structure for High-Dimensional Data », VLDB, Morgan Kaufmann Publishers Inc., vLDB '96,‎ 1^er janvier 1996 (ISBN 1-55860-382-4, lire en ligne)
↑ Jon Louis Bentley, « Multidimensional Binary Search Trees Used for Associative Searching », Commun. ACM, vol. 18,‎ 1^er septembre 1975 (ISSN 0001-0782, DOI 10.1145/361002.361007, lire en ligne)
↑ John T. Robinson, « The K-D-B-tree: A Search Structure for Large Multidimensional Dynamic Indexes », SIGMOD, ACM, sIGMOD '81,‎ 1^er janvier 1981 (ISBN 0-89791-040-0, DOI 10.1145/582318.582321, lire en ligne)
↑ (en) Octavian Procopiuc, Pankaj K. Agarwal, Lars Arge et Jeffrey Scott Vitter, Bkd-Tree: A Dynamic Scalable kd-Tree, Springer Berlin Heidelberg, coll. « Lecture Notes in Computer Science », 24 juillet 2003 (ISBN 978-3-540-40535-1 et 978-3-540-45072-6, DOI 10.1007/978-3-540-45072-6_4, lire en ligne)
↑ (en) R. A. Finkel et J. L. Bentley, « Quad trees a data structure for retrieval on composite keys », Acta Informatica, vol. 4,‎ 1^er mars 1974 (ISSN 0001-5903 et 1432-0525, DOI 10.1007/BF00288933, lire en ligne)
↑ Donald R. Morrison, « PATRICIA—Practical Algorithm To Retrieve Information Coded in Alphanumeric », J. ACM, vol. 15,‎ 1^er octobre 1968 (ISSN 0004-5411, DOI 10.1145/321479.321481, lire en ligne)
↑ Tilmann Zäschke, Christoph Zimmerli et Moira C. Norrie, « The PH-tree: A Space-efficient Storage Structure and Multi-dimensional Index », SIGMOD, ACM, sIGMOD '14,‎ 1^er janvier 2014 (ISBN 978-1-4503-2376-5, DOI 10.1145/2588555.2588564, lire en ligne)

[1] Antonin Guttman, « R-trees: A Dynamic Index Structure for Spatial Searching », SIGMOD, ACM, sIGMOD '84,‎ 1^er janvier 1984 (ISBN 0-89791-128-8, DOI 10.1145/602259.602266, lire en ligne)

[2] Ibrahim Kamel et Christos Faloutsos, « Hilbert R-tree: An Improved R-tree Using Fractals », VLBD, Morgan Kaufmann Publishers Inc., vLDB '94,‎ 1^er janvier 1994 (ISBN 1-55860-153-8, lire en ligne)

[3] Stefan Berchtold, Daniel A. Keim et Hans-Peter Kriegel, « The X-tree: An Index Structure for High-Dimensional Data », VLDB, Morgan Kaufmann Publishers Inc., vLDB '96,‎ 1^er janvier 1996 (ISBN 1-55860-382-4, lire en ligne)

[4] Jon Louis Bentley, « Multidimensional Binary Search Trees Used for Associative Searching », Commun. ACM, vol. 18,‎ 1^er septembre 1975 (ISSN 0001-0782, DOI 10.1145/361002.361007, lire en ligne)

[5] John T. Robinson, « The K-D-B-tree: A Search Structure for Large Multidimensional Dynamic Indexes », SIGMOD, ACM, sIGMOD '81,‎ 1^er janvier 1981 (ISBN 0-89791-040-0, DOI 10.1145/582318.582321, lire en ligne)

[6] (en) Octavian Procopiuc, Pankaj K. Agarwal, Lars Arge et Jeffrey Scott Vitter, Bkd-Tree: A Dynamic Scalable kd-Tree, Springer Berlin Heidelberg, coll. « Lecture Notes in Computer Science », 24 juillet 2003 (ISBN 978-3-540-40535-1 et 978-3-540-45072-6, DOI 10.1007/978-3-540-45072-6_4, lire en ligne)

[7] (en) R. A. Finkel et J. L. Bentley, « Quad trees a data structure for retrieval on composite keys », Acta Informatica, vol. 4,‎ 1^er mars 1974 (ISSN 0001-5903 et 1432-0525, DOI 10.1007/BF00288933, lire en ligne)

[8] Donald R. Morrison, « PATRICIA—Practical Algorithm To Retrieve Information Coded in Alphanumeric », J. ACM, vol. 15,‎ 1^er octobre 1968 (ISSN 0004-5411, DOI 10.1145/321479.321481, lire en ligne)

[9] Tilmann Zäschke, Christoph Zimmerli et Moira C. Norrie, « The PH-tree: A Space-efficient Storage Structure and Multi-dimensional Index », SIGMOD, ACM, sIGMOD '14,‎ 1^er janvier 2014 (ISBN 978-1-4503-2376-5, DOI 10.1145/2588555.2588564, lire en ligne)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

Famille R-Tree

R-Tree[1]

Structure

Propriétés

Hilbert R-Tree[2]

Nœuds

Scission

X-Tree[3]

Super-nœuds

Famille Kd-Tree

Kd-Tree[4]

Structure

Propriétés

KDB-Tree[5]

Propriétés

BKD-Tree[6]

Famille Quad-Tree

Quad-Tree[7]

Structure

Propriétés

Famille Patricia-Tree

Patricia-Tree[8]

Structure

Propriétés

Famille PH-Tree

PH-Tree[9]

Structure

Propriétés

Comparatif

Références

R-Tree^[1]

Hilbert R-Tree^[2]

X-Tree^[3]

Kd-Tree^[4]

KDB-Tree^[5]

BKD-Tree^[6]

Quad-Tree^[7]

Patricia-Tree^[8]

PH-Tree^[9]