R-Tree to GIST

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

R-Tree to GIST

Vladimir Voznesensky
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
Reply | Threaded
Open this post in threaded view
|

Re: R-Tree to GIST

Adam Wulkiewicz
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
Reply | Threaded
Open this post in threaded view
|

Re: R-Tree to GIST

Vladimir Voznesensky
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
Reply | Threaded
Open this post in threaded view
|

Re: R-Tree to GIST

Adam Wulkiewicz
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