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=(x0,... ,xK−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[modifier | modifier le code]
Un arbre kd relaxé pour un ensemble d'étiquettes à K-dimensions est un arbre binaire dans lequel :
- Chaque nœud contient une donnée à K-dimensions et a, associé, un discriminant arbitraire j ∈ {0,1,...,K − 1}.
- 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 yj < xj et n'importe quelle donnée dans le sous-arbre gauche avec l'étiquette y satisfait yj ≥ xj.[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,yi] × ... × [0,1], et ainsi de suite.
Requêtes supportées[modifier | modifier le code]
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(n1−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[modifier | modifier le code]
- (en) Amalia Duch, Vladimir Estivill-Castro et Conrado Martínez, Randomized K-Dimensional Binary Search Trees, Springer Berlin Heidelberg, coll. « Lecture Notes in Computer Science », , 478 p. (ISBN 978-3-540-65385-1, DOI 10.1007/3-540-49381-6_22, lire en ligne)
- (en) Amalia Duch et Conrado Martínez, « Improving the Performance of Multidimensional Search Using Fingers », ACM Journal of experimental algorithms, vol. 10, (lire en ligne, consulté le )
- (en) Kyung-Yong Chwa et Oscar H. Ibarra, Algorithms and Computation : 9th International Symposium, ISAAC'98, Taejon, Korea, December 14-16, 1998, Proceedings, Berlin, Heidelberg, Springer, 202–203 p. (ISBN 978-3-540-49381-5, BNF 44693324, lire en ligne)
