Boost logo

Boost Users :

From: Jens Thiele (karme_at_[hidden])
Date: 2021-07-14 14:28:32

Adam Wulkiewicz via Boost-users <boost-users_at_[hidden]> writes:

> W dniu 13.07.2021 o 17:04, Jens Thiele via Boost-users pisze:
>> Another problem I face now is that each run produces different results
>> which is still correct (multiple linestrings might have the same
>> distance to some point) but I would prefer a reproducible result.
>> I guess the cause for this is that
>> rtree_t::const_query_iterator it=t->qbegin(idx::nearest(pt, tree_size));
>> returns an iterator where the order isn't stable.
>> Would it be difficult to fix the iteration order?
> The rtree can have different internal structure depending on balancing
> algorithm and the order of inserts. So unless you know that values are
> always inserted in the same order it's impossible to guarantee that
> the structure is going to be the same. Then the order is also
> determined by the internals of the iterator, how exactly the rtree is
> traversed, how nodes and values are prioritized based on distance. And
> yes, currently heap and sort is used and I plan to replace sort with
> minmax heap for performance. Neither of these is stable.
> But I don't understand what do you mean by "each run" and "stable
> order"? What the stability refers to? Could you give an example?

Problem solved. The details:

The test basically does the following:
1) create r-tree
2) knn search of some points to linestrings
3) repeat 2 and compare results

Now a few points have the same distance to multiple linestrings
and in those cases I saw some random ordering of the linestrings in the
knn search results.

it wasn't the query iterator that introduced that randomness it was the
priority queue in the case where linestrings had the same distance =>
priority. To break the tie I now additionally use the ID of the
linestring => no more random ordering.


Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at