[OSM-talk-fr] Index R*-Tree pour système embarqué

Philippe Verdy verdy_p at wanadoo.fr
Sam 7 Fév 21:54:48 UTC 2015


Le 6 février 2015 00:03, Frédéric Rodrigo <fred.rodrigo at gmail.com> a écrit :

>
> Le 5 févr. 2015 19:08, "Philippe Verdy" <verdy_p at wanadoo.fr> a écrit :
> >
> > Le test se base sur le fait que tes R*trees ne sont pas maintenus
> équilibrés en contenu, une règle commune aux B-trees).
> >
> > Et quitte à diviser un rectangle R*tree en deux quand il est plein, on a
> normalement intérêt à le couper de préférence sur sa dimension la plus
> grande pour répartir les points de chaque côté (mais si on veut optimiser,
> on fait le test de répartition sur une dimensio puis sur l'autre, et on
> choisit celle où le trait de découpe est plus près du milieu de cette
> dimension).
> > La charge des R*trees doit normalement être portée sur la répartition,
> lors de l'insertion (ou la suppression) des noeuds, pour qu'ensuite les
> recherches n'aient pas à le faire.
> >
> > Dans ce cas avec un Quadtree tu génères pleins de boites vides et les
> branches de l'arbre sont moins bien équilibrées, avec un seuil minimum de
> remplissage de 25% là où un R*Tree utilise un minimum de 50% (arrondi à
> l'unité inférieure) : si ton R*tree a une capacité maximale de 6 points ou
> sous-rectangles, et une capacité minimale de 3 points ou sous-rectangles,
> c'est à dire 50% pour la répartition la plus optimale, le nombre de boites
> à visiter ne dépend pas de la distribution des points dans les boites
> seulement traversées mais sans point, mais seulement du nombre total de
> points, et le nombre de boites à visiter est en O(log_6(N) où N est le
> nombre total de noeuds, alors que le Quad-Tree ajoute des tas de points
> artificiels au centre des boites traversées sans noeud et est seulement en
> O(.log_4(N+k*S)) où S est le nombre total de segments et k une variable
> liée à la distribution des longueurs de segments.
>
>
Les deux index que tu commentes sont en fait des cas particuliers des
B-arbres. Normalement tu devrais assurer pendant le remplissage que toutes
les branches vers les boites feuilles sont à la même profondeur : tu
descent au maximum pour trouver la boite qui matche, tu vois si elle a
encore de la place pour le noeud à y ajouter (sauf que dans tes deux arbres
les places sont dédiées géométriquement, avec une séparation horizontale et
une séparation verticale, soit au centre dans les quadtree, soit
arbitraire, du moment que les 4 noeuds peuvent tenir. S'il n'y a plus de
place, tu dois découper la boite en 4 et les réindexer aux boites parentes
et ses voisines pour les placer de la même façon, en tentant de conserver
le seuil minimum de remplissage. Même chose en suppression. Si tu ne fais
pas ça tes arbres sont très déséquilibrés : la méthode naïve (seulement
descendante) se contente de couper la boite feuille en 4 pour y créer  4
branches et s'arrête là. Ca va très vite en insertion, en revanche très
vite ton arbre est fortement déséquilibré.

L'optimisation d'un B-arbre consiste à compacter les noeuds de l'arbre de
façon transversale entre toutes les branches de même niveau de profondeur.
C'est long à faire en cours de modif mais c'est possible une fois l'arbre
rempli car on a des statistiques de poids total de chaque branche.
Il y a plein de littérature sur la manipulation des B-arbres depuis des
décennies et c'est employé depuis longtemps dans toutes les bases de
données pour gérer leurs index.
-------------- section suivante --------------
Une pièce jointe HTML a été nettoyée...
URL: <http://lists.openstreetmap.org/pipermail/talk-fr/attachments/20150207/a4002057/attachment.html>


Plus d'informations sur la liste de diffusion Talk-fr