Geometry Boost List: Re: [geometry] How to adapt to Aggregate Rtree

From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2019-10-14 00:47:27

Hi,

W dniu 13.10.2019 o 10:18, Zhe Li via Geometry pisze:
> I'm trying to use an aggregate-Rtree
> (https://link.springer.com/content/pdf/10.1007%2F3-540-47724-1_23.pdf) to
> quickly find out the number of records given a predicate.
Sorry, the article is behind the paywall so I can't read all of it. Do I 
understand correctly that what you want is to know how many geometries 
are there in the query region? And therefore it would be possible to 
store aggregated numbers of geometries covered by each node of the 
R-tree and later during the query access only this number and therefore 
avoiding searching deeper parts of the R-tree?
> Currently, I use the following code, but it will traverse every node it has,
> which is not the aggregate-Rtree manner (and quite inefficient).
>
> ============
> size_t cardinality = 0; // number of matches in set
> auto count_only =
> boost::make_function_output_iterator([&cardinality](bgi::rtree<MyPoint,
>    bgi::linear&lt;16>>::value_type const&) { ++cardinality; });
> Box query_region(MyPoint(-91, -181), MyPoint(91, 181));
> rtree.query(bgi::intersects(query_region), count_only);
> ============
>
> I'm wondering is there any method to fast adapt the boost Rtree to an
> aggregate-Rtree? Or can
> boost Rtree directly provide such functionality (I cannot find it through
> the document)?
It depends what parts of the functionality would you want to use. Do you 
use the associative part of the R-tree, i.e. insert() and remove() 
methods? Or do you only create the rtree once with a constructor and 
then perform queries multiple times?

Even if you use insert(), when the query is done WRT the creation of the 
R-tree? Would it be acceptable to update the R-tree with inserts, then 
traverse the whole R-tree updating the aggregates, and only after that 
perform the query? Or are inserts done as frequently as queries and 
therefore aggregating the information from lower-level nodes should be a 
part of insert()?

The complexity of the task depends what parts of the R-tree you need. If 
you do not need to modify the insertion and removal algorithms and only 
create the aggregates for the whole tree before performing queries it 
should be fairly simple. You'd have to define your own node types, tell 
the R-tree to use them by specializing some templates and write your own 
query algorithm and an algorithm updating the aggregates stored in all 
of the nodes of the R-tree. If you need to aggregate information during 
insertion and removal of elements this would require to modify or 
implement your insert and remove algorithms (based on existing ones). 
And if you want to go even further (which I'm not sure if it's covered 
by the article) and want to decide how the elements and nodes should be 
distributed across the R-tree structure based on aggregates different 
than the MBRs (the classic R-tree uses only MBRs to decide where the new 
elements should be inserted and how should the nodes be divided when 
there is overflow) it would require to write more algorithms called when 
balancing of the R-tree is done during insertion.

Adam