structure logique permettant de stocker des couples de données
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).
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.
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.
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.
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
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 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.
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 où est un élément du et 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
Exemple de KDB-tree
une région correspond quant à elle à l'ensemble de tous les points correspondant à , .
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 , 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.
Le Quad-Tree permet de diviser récursivement l'espace en parties. Le Quad-Tree est utilisé pour un espace à 2 dimensions, cependant le concept peut s’étendre à dimensions.
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 à 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 entiers.
Pour ce faire, le PH-Tree stocke des bits à la place des caractères.
↑Ibrahim Kamel et Christos Faloutsos, « Hilbert R-tree: An Improved R-tree Using Fractals », VLBD, Morgan Kaufmann Publishers Inc., vLDB '94, (ISBN1-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, (ISBN1-55860-382-4, lire en ligne)