Discussion :

[mlequim]

Hello,

Quelqu'un aurait t'il des informations sur comment balancer un 3d-tree ?
J'ai les algorithmes pour générer un arbre balancé à partir d'un ensemble de points, mais pas comment garder un arbre balancé après une insertion. Si vous avez des infos cela m'intéresse, ainsi qu'une implémentation. Idéallement je cherche une classe Java pour un 3D-tree balancé persistent mais si vous n'avez pas de version persistente ce n'est pas grâve je le rajouterai.

[Jean-Marc.Bourguet]

Quelqu'un aurait t'il des informations sur comment balancer un 3d-tree?

Si tu cherches a rester balance, je regarderais plutot les R-Trees. Je ne me souviens pas avoir vu d'algo de balancement incremental de kd-tree.

[mlequim]

C'est ce que je pensais aussi, mais le texte ci-dessous extrait de l'encyclopédie libre wikipédia me fait penser le contraire.

Balancing a kd-tree
Balancing a kd-tree requires care. Because kd-trees are sorted in multiple dimensions, the tree rotation technique cannot be used to balance them — this may break the invariant.

En lisant cela j'ai l'impression que le balancement par rotations n'est plus applicable mais qu'il existe une autre méthode.

Je ne connais pas les R-tree, tu as plus d'infos dessus ?


Ce que je veux faire c'est créér un programme de modélisation pour le plaisir, j'étudie pour le moment les structures de données que je vais utiliser. J'ai pensé utiliser un kd-tree pour stoquer les vertices car c'est une structure qui à de bonnes performances pour la recherche. Il existe des algorithmes qui peuvent efficacement effectuer des range-search ce qui me permettrait de facilement faire un outil de sélection, et en rajoutant de la persistence je pourrais faire un undo pas trop couteux en place mémoire. Aurais tu un lien qui comparerait les complexités des R-tree et des kd-tree pour ces opérations (recherche élément, range-searching, insertion balancée) ?[/quote]

[GrandFather]

Bonjour,

Je ne connais pas les R-tree, tu as plus d'infos dessus ?

Une implémentation de R-Tree en Java : http://www.fzg.uni-osnabrueck.de/mitarbeiter/baer/rtree.html

Tu trouveras sur la même page un document PDF décrivant l'algorithme des R-Tree par leur inventeur, A. Guttman.

[Jean-Marc.Bourguet]

Aurais tu un lien qui comparerait les complexités des R-tree et des kd-tree pour ces opérations (recherche élément, range-searching, insertion balancée)?

Quelques papiers trouvables sur le net (en particulier citesearch mais mettre simplement les titres dans google doit permettre de trouver la plupart). J'avais fait cette liste en 2002-2003; les commentaires sont de moi. Les 3 derniers papiers ne concernent pas l'utilisation incrementale. J'avais fini par utiliser la variante "fractale" (c'etait pour le cas 2 dimentions)

*) A. Guttman
R-trees: A dynamic index structure for spatial searching
Proc. SIGMOD, 1984.
rtrees.pdf

The foundation paper.

*) T. Sellis et al.
The R+ tree: a dynamic index for multi-dimensional objects.
Proc. 13th International Conference on VLDB, pp 507-518
also available as SRC-TR-87-32, UMIACS-TR-87-3, CS-TR-1795
R+-tree.pdf

*) D. Greene
An implementation and performance analysis of spatial data access
methods.
Proc. of Data Engineering, pp 606-615
greene.pdf

An analysis of performance of R-Trees (in fact a variant even if it
is presented as the original one), R+-Trees and some earlier
methods.

*) N. Beckmann et al.
The R*-tree: An efficient and robust access method for points and
rectangles
Proc. SIGMOD, 1990.
rstartrees.pdf

Variant (keep the data structure, change some sub-parts of the
algorithm) of rtree with better search characteristic. But more
complicated.

*) I. Kamel, C. Faloutsos
Hilbert R-tree: An improved R-tree using fractals
Proc. VLDB, 1994.
hilbert-rtrees.pdf

Variant (keep the data structure, change some sub-parts of the
algorithm) of rtree with better search characteristic even than
R*-Tree. But more complicated.

*) P. K. Agarwal et al.
Box-Trees and R-Trees with Near-Optimal Query Time
To appear in Discrete and Computational Geometry, 2002.
box.pdf

A recent paper. Very theorical. Establish bound and give an
algorithm but not very interesting in our case as they are for
construction from the scratch and not for incremental editing.
Usefull also for the given references.

-*-

*) J. van den Bercken et al.
A generic approach to bulk loading multidimensional index
structures
Proc. VLDB, 1997.
bulk.pdf

*) Y. J. Garcia et al.
A greedy algorithm for bulk-loading R-trees
Tech. rept., Univ. of Denver, 1997. Poster on ACM-GIS '98.
greedy-bulk.ps

[mlequim]

A dynamic index structure for spatial searching

ça à l'air de correspondre à mes besoins,...

merci pour ces documents

juste pour ma culture générale, quelqu'un pourrait'il me confirmer que les kd-tree n'ont pas d'algorithme de construction incrémental ?

même si les R-tree ont plus l'air adapté à mon besoin j'aimerais avoir cette réponse par pure curiositée

[mlequim]

Bonjour,

Je ne connais pas les R-tree, tu as plus d'infos dessus ?

Une implémentation de R-Tree en Java : http://www.fzg.uni-osnabrueck.de/mitarbeiter/baer/rtree.html

Tu trouveras sur la même page un document PDF décrivant l'algorithme des R-Tree par leur inventeur, A. Guttman.

merci à toi aussi pour ce lien, ça va me faire gagner un temps fou !