Re: [OSM-talk-fr] Index R*-Tree pour système embarqué
Le 6 février 2015 00:03, Frédéric Rodrigo fred.rodr...@gmail.com a écrit : Le 5 févr. 2015 19:08, Philippe Verdy verd...@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. ___ Talk-fr mailing list Talk-fr@openstreetmap.org https://lists.openstreetmap.org/listinfo/talk-fr
Re: [OSM-talk-fr] Index R*-Tree pour système embarqué
Le 5 févr. 2015 19:08, Philippe Verdy verd...@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. Tu pourrais s'il te plait détailler ce denier point ? Ta as des sources pour ces complexités que tu pourrais citer, stp? 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 l...@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 -- Léo SERRE LSTRONIC Founder l...@lstronic.com lstronic.com ___ Talk-fr mailing list Talk-fr@openstreetmap.org https://lists.openstreetmap.org/listinfo/talk-fr ___ Talk-fr mailing list Talk-fr@openstreetmap.org https://lists.openstreetmap.org/listinfo/talk-fr ___ Talk-fr mailing list Talk-fr@openstreetmap.org https://lists.openstreetmap.org/listinfo/talk-fr
[OSM-talk-fr] Index R*-Tree pour système embarqué
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 -- LSTRONIC logo Léo SERRE /LSTRONIC Founder/ mail l...@lstronic.com mailto:l...@lstronic.com website lstronic.com http://lstronic.com ___ Talk-fr mailing list Talk-fr@openstreetmap.org https://lists.openstreetmap.org/listinfo/talk-fr
Re: [OSM-talk-fr] Index R*-Tree pour système embarqué
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 l...@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] l...@lstronic.com [image: website] lstronic.com ___ Talk-fr mailing list Talk-fr@openstreetmap.org https://lists.openstreetmap.org/listinfo/talk-fr ___ Talk-fr mailing list Talk-fr@openstreetmap.org https://lists.openstreetmap.org/listinfo/talk-fr
Re: [OSM-talk-fr] Index R*-Tree pour système embarqué
Pour une donnée en 2D, le quad tree est en effet plus adapté à ce qu'il me semble... Le 05/02/2015 18:20, Léo Serre 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 -- LSTRONIC logo Léo SERRE /LSTRONIC Founder/ mail l...@lstronic.com mailto:l...@lstronic.com website lstronic.com http://lstronic.com ___ Talk-fr mailing list Talk-fr@openstreetmap.org https://lists.openstreetmap.org/listinfo/talk-fr -- Christian Quest - OpenStreetMap France ___ Talk-fr mailing list Talk-fr@openstreetmap.org https://lists.openstreetmap.org/listinfo/talk-fr
