Another strange question, please. Currently, rtree code deals with continious data values. Each value is treated as a spatial coordinate. The question is: would it be painful to treat some coodinates as 32, 64 or 128 bits bitsets? In other words, is it possible to refactor R-Tree to Generalized Index Search Tree? Without messing too much the code, of course, Thanks.
_______________________________________________ Geometry mailing list [hidden email] http://lists.boost.org/mailman/listinfo.cgi/geometry |
Hi Vladimir,
Vladimir Voznesensky wrote: > Another strange question, please. > Currently, rtree code deals with continious data values. Each value is > treated as a spatial coordinate. The question is: would it be painful > to treat some coodinates as 32, 64 or 128 bits bitsets? In other > words, is it possible to refactor R-Tree to Generalized Index Search Tree? > Without messing too much the code, of course, Sorry, but I'm not a GiST expert, besides this looks like a specific case. AFAIU you'd like to perform the indexing and querying differently than it's done by the R-tree. Could you please explain what would you like to do exactly? Regards, Adam _______________________________________________ Geometry mailing list [hidden email] http://lists.boost.org/mailman/listinfo.cgi/geometry |
GiST could be seen as a generalization of R-tree. In the common case, tree internal nodes are not restricted to describe their subtrees by bounding rectangular boxes. Some things could be described by ellipsoids or, even more exotic, by Bloom filters.
I would like to add some traits defining algorithms for calculation of: - Subtrees overlapping cost; - Insertion cost and resulting internal node subtree aggregate; - Querying criteria. User could also need to have weighted points and be able to calculate an overall sum weight of all points in a given region, so internal tree nodes could have aggregate weights of each subtree. 29.01.2016, 02:07, "Adam Wulkiewicz" <[hidden email]>: > Hi Vladimir, > > Vladimir Voznesensky wrote: >> Another strange question, please. >> Currently, rtree code deals with continious data values. Each value is >> treated as a spatial coordinate. The question is: would it be painful >> to treat some coodinates as 32, 64 or 128 bits bitsets? In other >> words, is it possible to refactor R-Tree to Generalized Index Search Tree? >> Without messing too much the code, of course, > > Sorry, but I'm not a GiST expert, besides this looks like a specific > case. AFAIU you'd like to perform the indexing and querying differently > than it's done by the R-tree. Could you please explain what would you > like to do exactly? > > Regards, > Adam > _______________________________________________ > Geometry mailing list > [hidden email] > http://lists.boost.org/mailman/listinfo.cgi/geometry Geometry mailing list [hidden email] http://lists.boost.org/mailman/listinfo.cgi/geometry |
Please don't top-post. All Boost mailing lists discourages this.
Vladimir Voznesensky wrote: > GiST could be seen as a generalization of R-tree. In the common case, tree internal nodes are not restricted to describe their subtrees by bounding rectangular boxes. Some things could be described by ellipsoids or, even more exotic, by Bloom filters. > > I would like to add some traits defining algorithms for calculation of: > - Subtrees overlapping cost; > - Insertion cost and resulting internal node subtree aggregate; > - Querying criteria. > > User could also need to have weighted points and be able to calculate an overall sum weight of all points in a given region, so internal tree nodes could have aggregate weights of each subtree. I think doing the above should be possible out of the box, maybe with small changes. However everything I'm going to describe here sits in the details so it's not officially released interface. INSERTION: As you know the rtree along with Value takes Parameters. Those parameters are defined here: https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/index/parameters.hpp#L74 Based on Parameters passed into the rtree<> template algorithms and nodes are picked, this is done here: https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/index/detail/rtree/options.hpp So by specialization of options_type<> struct for some specific Parameters the following is defined: 1. inserting algorithm - high level part of insertion algorithm, there are 2 implemented: - default one simply inserting new value - https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/index/detail/rtree/visitors/insert.hpp#L230 - forcibly reinserting one on overflow used by the R*-tree - https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/index/detail/rtree/rstar/insert.hpp 2. subtrees choosing algorithm - an algorithm choosing the best subtree while inserting, there are 2 implemented: - used by classic R-tree variants - https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/index/detail/rtree/visitors/insert.hpp#L30 - used by R*-tree - https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/index/detail/rtree/rstar/choose_next_node.hpp 3. splitting algorithm - an algorithm splitting elements of a node into 2 nodes - currently only one version is implemented, creating an additional node and calling redistribution algorithm - https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/index/detail/rtree/visitors/insert.hpp#L114 4. redistribution algorithm - an algorithm redistributing elements stored in one node into 2 nodes or rather as many nodes as aplitting algorithm requires (currently 3) - Guttman's linear - https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/index/detail/rtree/linear/redistribute_elements.hpp#L309 - Guttman's quadratic - https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/index/detail/rtree/quadratic/redistribute_elements.hpp#L84 - R*-tree - https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/index/detail/rtree/rstar/redistribute_elements.hpp#L368 5. nodes - the internal structure of nodes, (currently 2) - storing dynamic-sized containers of elements - https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/index/detail/rtree/node/variant_dynamic.hpp - storing static-sized containers of elements - https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/index/detail/rtree/node/variant_static.hpp So you could create your own Parameters, specialize whatever algorithms you like, at any level, then specialize options_type<> in order to bind Parameters with your algorithms and it should work. Just keep in mind that you're messing with details which may be changed in the future, though I think if they was changed in the future it would not be a radical change. QUERYING: As for querying, you could write your own tree visitor but I guess it would be enough to write and support your own predicate. And the way how this would be done depends slightly on what you'd like to do exactly. But let's keep it simple and consider spatial predicates, for instance intersects(). Here is a function returning predicate object (for convenience): https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/index/predicates.hpp#L169 here are tags and spatial_predicate class: https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/index/detail/predicates.hpp#L58 then predicate checking struct is specialized: - for values stored in leafs - https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/index/detail/predicates.hpp#L236 - for nodes bounding boxes - https://github.com/boostorg/geometry/blob/develop/include/boost/geometry/index/detail/predicates.hpp#L312 So again, you should be able to specialize those and they would be used by the default query visitor. Regards, Adam _______________________________________________ Geometry mailing list [hidden email] http://lists.boost.org/mailman/listinfo.cgi/geometry |
Free forum by Nabble | Edit this page |