Arbre kd relaxé

Un arbre kd relaxé ou arbre à k-dimension relaxé est une structure de données qui est une variante de l'arbre kd. Comment les arbres kd, un arbre kd relaxé stocke un ensemble de données à n-dimensions, chacune ayant une unique étiquette à K-dimensions x=(x₀,... ,x_K−1). Contrairement aux arbres kd, dans un arbre kd relaxé, le discriminant dans chaque nœud est arbitraire. Les arbres kd relaxés ont été introduits en 1998^[1].

Définitions

Un arbre kd relaxé pour un ensemble d'étiquettes à K-dimensions est un arbre binaire dans lequel :

1. Chaque nœud contient une donnée à K-dimensions et a, associé, un discriminant arbitraire j ∈ {0,1,...,K − 1}.
2. Pour chaque nœud avec l'étiquette x et le discriminant j, l'invariant suivant est vrai : n'importe quelle donnée dans le sous-arbre droit avec l'étiquette y satisfait y_j < x_j et n'importe quelle donnée dans le sous-arbre gauche avec l'étiquette y satisfait y_j ≥ x_j.^[2]

Si K=1, un arbre kd relaxé est un arbre binaire de recherche.

Comme dans un arbre kd, un arbre kd relaxé de taille n induit une partition du domaine D en n+1 régions, chacune correspondant à une feuille dans l'arbre kd. La zone de délimitation (ou délimitation du tableau) d'un nœud {x,j} est la région de l'espace délimitée par la feuille dans laquelle x tombe quand il est inséré dans l'arbre. Ainsi, la zone de délimitation de la racine {y,i} est [0,1]^K, la zone de délimitation de la racine du sous-arbre-gauche est [0,1] × ... × [0,y_i] × ... × [0,1], et ainsi de suite.

Requêtes supportées

Le temps moyen des complexités dans un arbre kd relaxé avec n données sont :

• Requête de correspondance parfaite : O(log n)
• Requête de correspondance partielle : O(n^1−f(s/K)), où :
  • s parmi K attributs sont spécifiés
  • avec 0 < f(s/K) < 1, une fonction à réelle valeur de s/K
• Requête de plus proches voisins : O(log n)^[3]

Références

• Portail des mathématiques