Problem with building OSM Europe with inner-outer-geoms

[ad-freiburg]

Problem with building OSM Europe with inner-outer-geoms

[hannahbast]

Just testing "creating an issue from project"

[patrickbr]

I was finally able to reproduce this in gdb. As suspected, it is a stack overflow in

osm2rdf/src/util/DirectedGraph.cpp

Line 53 in 03cc182

void osm2rdf::util::DirectedGraph<T>::findSuccessorsHelper(

This is a recursive function which produces all successors for a given node in a DAG. As the graph is assumed to be acyclic, nodes are not marked as visited. For some reason, a cycle is introduced for europe-latest.osm, and this recursion never ends. The code that builds the DAG has an explicit check if two areas A and B are equivalent (https://github.com/ad-freiburg/osm2rdf/blob/inner-outer-geoms/src/osm/GeometryHandler.cpp#L589), and if so, does not insert any edge between the corresponding nodes in the DAG. This is to avoid adding two edges A -> B and B -> A and thus introducing a cycle. If for some reason (floating point inaccuracies?) it holds that both A in B and B in A, but A != B, a cycle will be inserted into the graph. I strongly suspect that is what happens here.

After talking with Axel, we have two suspicions why this only happens on europe-latest.osm, and not planet.osm.

1.) Different data sources. europe-latest.osm is from Geofabrik and has been touched by at least one filtering tool, possibly adding slight floating point inaccuracies, while planet.osm is a raw export from OSM.
2.) The insertion order might be different, and/or areas already present in the DAG might prevent adding the erroneous edge.

The obvious solution to check whether an edge B -> A is present in the graph if A -> B is about to be added will not work, as it is still possible to produce a cycle A -> B -> C -> A. We should instead replace the equivalence check (boost::geometry::equal(a, b)) in https://github.com/ad-freiburg/osm2rdf/blob/inner-outer-geoms/src/osm/GeometryHandler.cpp#L589 by boost::geometry::covered_by(a, b) && boost::geometry::covered_by(b, a), thus using the exact same algorithm for checking equivalency as for checking whether the areas are contained in each other.

I will test this today on ob.

[patrickbr]

Now running on ob, log goes to /local/data/brosip/osm2rdf.log.

[hannahbast]

@patrickbr @lehmann-4178656ch Wow, thanks for looking into this + looking forward to the outcome!

[patrickbr]

With e0ae455 the DAG build for europe-latest.osm was successful and took 4 hours and 37 minutes. Currently building the node-in-area relations.

[patrickbr]

Quick update: run with full geometries on europe-latest.osm has finished and took 4.5 days. Run with --approximate-spatial-relations has been started, log goes to /local/data/brosip/osm2rdf-approx.log.

[hannahbast]

Did the approx run crash or stall? The log file was last updated on 12.07.2022 at 13:45.

[patrickbr]

No, we stopped it because the weekly osm2rdf update was running at the same time, which would've resulted in incomparable running times. I restarted it a few minutes ago :)

[lehmann-4178656ch]

I restarted it a few minutes ago :)

Which is not that great for comparability as the weekly updates will start tommorrow evening.

[patrickbr]

My hope was that the run will be finished until tomorrow, but you are probably right that it won't :) wolga seems to be idling, I will start it there.