Geometry Boost List: Re: [geometry] R-Tree Nearest Neighbors Unique Member From Group

Subject: Re: [geometry] R-Tree Nearest Neighbors Unique Member From Group
From: Adam Wulkiewicz (adam.wulkiewicz_at_[hidden])
Date: 2018-05-16 17:34:31

Hi,

Jpb Via Geometry wrote:
> Hi Guys,
>
> I have an rtree where each item in the tree has a group ( Colors perhaps:
> red, green, blue, orange...)
> I want to do a nearest neighbor search where the search returns the nearest
> k-neighbors with at most
> one object from each group.
>
> For example, if we have
>
> Object A: Red,    distance 1
> Object B: Red,    distance 2
> Object C: Blue,   distance 3
> Object D: Green, distance 4
>
> and I do a nearest neighbor at most one from each group search with k = 2
> then
> I get object A and C. B is skipped since A is closer of the same group.
>
> It looks like I could get this done by creating a specialization of
> distance_query_result class and have the distance_query_result::store method
> to check the groups/distances of already stored items and act accordingly.
> Then create a specialization of distance query and maybe query_dispatch to
> get distance_query to use the new distance_query_result.
>
> Is there a better way to go about this?

No, there is no "official" (i.e. exposed in the interface) way of doing 
it besides calling query N times for each group/category (using 
nearest() && satisfies()) and after that merging the results. So your 
approach is more optimal than that however it relies on the internals of 
the R-tree so have in mind that they may be changed some time in the future.

I'd suggest keeping N stacks (neighbors) one for each group and track 
them separately.
You also have to somehow pass the number of groups into the 
distance_query_result.
Furthermore you have to implement 
distance_query_result::greatest_comparable_distance() and return the 
greatest distance from all groups but only if all heaps contain at least 
one element each.

But I'm wondering, are the elements from all groups distributed more or 
less in uniform fashion? I'm asking because otherwise the query may have 
to traverse big chunks of the tree before finding at least one element 
from each group. Consider the situation where there is a clear 
separation between groups and groups are spatially far from each other. 
In this case my guess is that it'd be better to have separate R-tree for 
each group, perform knn query on all of them and merge the results.

An alternative to the solution above (for groups spatially far from each 
other) would be to have one R-tree but to store in the nodes the 
information about the groups of objects sotred in underlying nodes and 
custom query visitor taking into account currently stored neaighbors and 
groups covered by analysed nodes. So the idea is that the pruning of 
nodes would be done both using the distance to the furthest neighbor 
already found as well as groups of neighbors. This would not require to 
merge the result at the end since the query woudl handle everything. But 
it would require even more changes to the R-tree including introducing 
new nodes (containing info about underlying groups), insertion visitor 
(gathering the info about the groups from children and passing it to the 
newly created node) and packing algorithm (if needed, the same as 
insertion).

Regards,
Adam