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

Philippe Verdy verdy_p at wanadoo.fr
Jeu 5 Fév 18:07:33 UTC 2015


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.

C'est pour ça que dans le cas totalement aléatoire (ton premier test), le
QuadTree s'écroule totalement : il crée beaucoup trop de sous-boites, et la
profondeur de l'arbre de recherche s'accroit énormément. Le R*Tree
produirait un nombre de boites bien plus réduit (à condition de le régler à
un taux de remplissage minimum de 50% arrondi à l'unité inférieure).

Il doit y avoir un problème dans ton logiciel insérant les points dans le
R*Tree, il n'est visiblement pas optimal comme il devrait.

De fait les R*trees obtenus sont très "étranges" (et ça se voit, la
répartition est visiblement n'importe comment et spatialement non
équilibrée, en tout cas beaucoup moins bien que celle obtenue par les
Quad-trees même si, eux, créent plein de boites finales vides et de boites
parentes n'a qu'une seule des 4 ayant un contenu, avec un taux de
remplissage situé en moyenne à peine au dessus de 25% contre plus de 50% en
moyenne pour les R*trees optimums).

Note: le seuil minimum des R*tree est réglable (tu l'as fait dans ta démo,
mais je me demande si c'est bien le cas au final, et si tu n'as pas omis de
lancer la procédure d'équilibrage (qu'on a intérêt à ne lancer qu'à la fin
des insertions et non pour chaque insertion une par une).


Le 5 février 2015 18:20, Léo Serre <leo at lstronic.com> a écrit :

>  Bonjour à tous
>
> Après de longues recherches pour savoir qu'elle est l'indexation la plus
> efficace (simplicité de construction, rapidité pour trouver un élément,
> taille), tout le monde m'a dit R*-Tree.
> Mais après des essais, ma conclusion est que le quadtree est largement
> mieux. Je vous laisse un exemple en vidéo ci-dessous pour ceux que ça
> intéresse.
>
>
> http://www.dailymotion.com/video/x2ghtqj_r-tree-pour-des-donnees-geographiques_tech
>
> *Note : Le code pour convertir des LineString GeoJSON **en Segments CSV
> est disponible sur simple demande.*
>
> Léo
>
> --
> [image: LSTRONIC logo]
>
> Léo SERRE
> *LSTRONIC Founder*
> [image: mail]  leo at lstronic.com
> [image: website]  lstronic.com
>
> _______________________________________________
> Talk-fr mailing list
> Talk-fr at openstreetmap.org
> https://lists.openstreetmap.org/listinfo/talk-fr
>
>
-------------- section suivante --------------
Une pièce jointe HTML a été nettoyée...
URL: <http://lists.openstreetmap.org/pipermail/talk-fr/attachments/20150205/c2123d7b/attachment-0001.html>
-------------- section suivante --------------
Une pièce jointe autre que texte a été nettoyée...
Nom: hdbgefga.png
Type: image/png
Taille: 150 octets
Desc: non disponible
URL: <http://lists.openstreetmap.org/pipermail/talk-fr/attachments/20150205/c2123d7b/attachment-0003.png>
-------------- section suivante --------------
Une pièce jointe autre que texte a été nettoyée...
Nom: cidebaic.png
Type: image/png
Taille: 2842 octets
Desc: non disponible
URL: <http://lists.openstreetmap.org/pipermail/talk-fr/attachments/20150205/c2123d7b/attachment-0004.png>
-------------- section suivante --------------
Une pièce jointe autre que texte a été nettoyée...
Nom: ejhcihja.png
Type: image/png
Taille: 297 octets
Desc: non disponible
URL: <http://lists.openstreetmap.org/pipermail/talk-fr/attachments/20150205/c2123d7b/attachment-0005.png>


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