DuplicateWayRemover removes ways even if the tags don't match

[bwitham]

ported from redmine 2335

There is no logic in DuplicateWayRemover to check for matching tags. For instance the DC data has a bunch of duplicate records where the only difference is the road name. The DuplicateWayRemover should be able to do two things:

If the only difference is in naming, merge the names.
If the difference is more substantial then don't perform the merge. Although this should be a tunable parameter through the conf file.

[bwitham]

@jasonsurratt I just realized how old this task is as I'm writing this... Do you remember at all what DC data had duplicate ways with differing names? All the ways I'm seeing in DC streets with two or more shared nodes have exact name matches so far...I may be just missing them somehow. Also looked at some other datasets and haven't found this situation pop up. If I can't find any data as described, I'll pass on this one for now. TIA

[jasonsurratt]

Look at test-files/DcTigerRoads.osm (Sorry, I should have been more explicit).

[bwitham]

Awesome. thanks. That was the data I was looking at before, but wasn't seeing it get flagged in DuplicateWayRemover as having common nodes...definitely should be though...so I'll debug through again looking specifically for that road pair.

[bwitham]

Found this situation in the larger dc streets data and cropped down to the small area by the ellipse for testing. The only thing is that Constitution Ave NW and US Hwy 50 share no nodes in common in this example, so the DuplicateWayRemover does not see them as duplicates even though one road overlays directly on top of the other. Is there some other criteria that can be used to identify the two roads as duplicates?

[jasonsurratt]

Brandon and I chatted on the phone and I think he is sorted out now.

[bwitham]

Yes, problem caused by inadvertent commit of changes to DcTigerRoads.osm on a branch....amateur hour :-) Thanks, Jason. Reproduced situation in data and am working on solution now.

[bwitham]

Changes done. running regression tests.

[bwitham]

@jasonsurratt Do you mind taking a look at this when you have a chance? I think I've accomplished the goal of this task...retaining provenance of name tags that were previously lost b/c of the DuplicateWayRemover, as well as preventing duplicate way removal when there are non-name tag differences in the ways (configurable). In DcTigerRoads, the Constitution Ave / US 50 example seems to be handled properly now (US Hwy 50 goes into alt_name now). The other one I used as a reference case and paid special attention to was the portion of Pennsylvania Ave that runs along with 15th street (Pennsylvania Ave goes into alt_name now). I also briefly checked all the other new name tag merges in the DcTigerRoads, and they looked ok to me. Changed a lot of slow/glacial test output...for the most part name tag changes only (makes sense), but the hadoop test file output changes were a little harder for me to verify (think they're ok??). Regression tests are in good shape so far too (two still running). Thanks.

[jasonsurratt]

Yup. I just started running the tests locally now. I'll take a peek tomorrow.

[jasonsurratt]

Are these the Hadoop tests you were referring to? If so I'll take a closer look in the morning.

14:50:47.903 WARN  ...core/scoring/MapComparator.cpp( 178) rn: -77.032012700000010, 38.886043400000005 n: -77.032034800000005, 38.886044000000005
14:50:47.903 WARN  ...core/scoring/MapComparator.cpp(  98) Did not find element: Node:170
14:50:47.903 WARN  ...core/scoring/MapComparator.cpp( 178) rn: -77.032034800000005, 38.886044000000005 n: -77.032012700000010, 38.886043400000005
14:50:47.904 WARN  ...core/scoring/MapComparator.cpp(  98) Did not find element: Node:422
14:50:47.938 WARN  ...core/scoring/MapComparator.cpp( 123) Tags do not match:
14:50:47.938 WARN  ...core/scoring/MapComparator.cpp( 136) < alt_name = 14TH ST SW;US Hwy 1
14:50:47.938 WARN  ...core/scoring/MapComparator.cpp( 137) > alt_name = 14TH ST SW
14:50:47.939 WARN  ...core/scoring/MapComparator.cpp( 123) Tags do not match:
14:50:47.939 WARN  ...core/scoring/MapComparator.cpp( 136) < alt_name = K ST NW;US Hwy 29
14:50:47.939 WARN  ...core/scoring/MapComparator.cpp( 137) > alt_name = K ST NW
14:50:47.939 WARN  ...core/scoring/MapComparator.cpp( 123) Tags do not match:
14:50:47.939 WARN  ...core/scoring/MapComparator.cpp( 136) < alt_name = K ST NW;US Hwy 29
14:50:47.939 WARN  ...core/scoring/MapComparator.cpp( 137) > alt_name = K ST NW
14:50:47.939 WARN  ...core/scoring/MapComparator.cpp(  98) Did not find element: Way:15828
14:50:47.941 WARN  ...core/scoring/MapComparator.cpp(  98) Did not find element: Way:20877
14:50:47.942 WARN  ...core/scoring/MapComparator.cpp(  98) Did not find element: Way:20881
14:50:47.942 WARN  ...core/scoring/MapComparator.cpp(  98) More than 10 errors, suppressing errors.
F
Failure: hoot::HadoopTileWorkerTest::testAll
  src/test/cpp/hoot/hadoop/HadoopTileWorkerTest.cpp(97)   - Maps do not match: test-files/hadoop/HadoopTileWorkerTest/result.osm test-output/hadoop/HadoopTileWorkerTest/result.osm
..14:52:18.699 WARN  ...core/scoring/MapComparator.cpp( 178) rn: -77.048758988475925, 38.902566032708997 n: -77.048762591981344, 38.902551612741213
14:52:18.699 WARN  ...core/scoring/MapComparator.cpp( 178) rn: -77.048762591981344, 38.902551612741213 n: -77.048758988475925, 38.902566032708997
14:52:18.722 WARN  ...core/scoring/MapComparator.cpp( 123) Tags do not match:
14:52:18.722 WARN  ...core/scoring/MapComparator.cpp( 136) < alt_name = K St NW
14:52:18.722 WARN  ...core/scoring/MapComparator.cpp( 137) > alt_name = K St NW;US Hwy 29
14:52:18.727 WARN  ...core/scoring/MapComparator.cpp( 123) Tags do not match:
14:52:18.727 WARN  ...core/scoring/MapComparator.cpp( 136) < alt_name = K St NW
14:52:18.727 WARN  ...core/scoring/MapComparator.cpp( 137) > alt_name = K St NW;US Hwy 29
14:52:18.727 WARN  ...core/scoring/MapComparator.cpp(  98) Did not find element: Way:-34043
14:52:18.727 WARN  ...core/scoring/MapComparator.cpp(  98) Did not find element: Way:-34040
14:52:18.728 WARN  ...core/scoring/MapComparator.cpp( 123) Tags do not match:
14:52:18.728 WARN  ...core/scoring/MapComparator.cpp( 136) < alt_name = K St NW
14:52:18.728 WARN  ...core/scoring/MapComparator.cpp( 137) > alt_name = K St NW;US Hwy 29
F
Failure: hoot::TileConflatorTest::runToyTest
  src/test/cpp/hoot/core/conflate/TileConflatorTest.cpp(86)   - Expected: 1
- Actual  : 0

[bwitham]

Yeah, those two were the hadoop test affects....tag differences seem ok, but the "Did not find element" messages worry me a bit, which must be due to ways which now aren't being merged as a result of the DuplicateWayRemover changes (?).

[bwitham]

Actually, I thought I had already checked in the updated test files...so surprised you saw the errors, but maybe I forgot to.

[jasonsurratt]

I am getting inconssitent results on test runs for hoot::HadoopTileWorkerTest::testAll and hoot::TileConflatorTest::runToyTest. I haven't dug into why, but could there be something in the duplicate way code that is causing inconsistent results?

[bwitham]

Ok, interesting. I checked and I did commit test output updates for those two already. But that might explain why you got those errors on one run. I need to run a couple times in a row and see if I see them.

I can't think of anything that would cause any randomness in DuplicateWayRemover, but let me think about it. I also have an interesting bit of code to show you which may be related. It has to do with I was loading my test data with OsmReader and getting one set of results with DuplicateWayRemover vs getting a completely different result output when I used OsmReaderFactory::read (like I ended up having to do in DuplicateWayRemoverTest). I'm sure there's a logical explanation, but just haven't been able to track down yet. Helping Mitul with the release scripts right now, but may send you that code example later today to see what you think. I'll also dig into the hadoop test output myself.

[jasonsurratt]

Shooting from the hip -- are the node ids being [not] renumbered consistently between the two read operations. Let me know if you want me to dig deeper.

https://insightcloud.digitalglobe.com/redmine/projects/hootenany/wiki/Developer_-_Inconsistent_Output

[bwitham]

I could maybe see that being the difference between the the results I get running hoot convert with the DuplicateWayRemover as an op (output I expect) and maybe the different output in the hadoop operations if one was using OsmReader and the other OsmReaderFactory (not sure if they are). But still don't see how that could cause differences between runs of the same command. I'll look into it. Which of the common problems on that wiki page were you thinking could be causing the node id renumbering problem? An uninitialized variable?

[jasonsurratt]

I didn't have a specific idea in mind when I posted the wiki page. I just wanted to throw that out there b/c it has helped me in the past. For me these problems usually require a fair bit of diving into code to find the source of the problem.

[bwitham]

thanks, got it.

[bwitham]

reproduced intermittent test failures. Now attempting to determine the cause.

[bwitham]

Turning on uuid.helper.repeatable stabilizes the two tests with the new DuplicateWayRemover. So, seems to be evidence that the ways are being read in different orders at different times. This would explain the differing results, as different merges would be made by DuplicateWayRemover as it examined different pairs of ways per usage.

[bwitham]

Disregard previous statement...looking at wrong branch. TileWorkerTest failing intermittently and HadoopTileWorkerTest failing consistently with new code when setting uuid.helper.repeatable to true and unify.optimizer.time.limit to -1. So, at least now I have a baseline to begin with.

[bwitham]

I think OsmReader/OsmReaderFactory differences I mentioned are irrelevant to this problem, although it may be worth looking into as a separate issue (unless it was just me misusing the classes). In the new code, with uuid.helper.repeatable to true and unify.optimizer.time.limit to -1, tests fail about four out of every five runs or so. With debug logging on, the only difference between output between a passing test and a failing test is a single different node ID in the tile worker code that replaces nodes in relations. The DuplicateWayRemover seems to be making the same decisions on ways in both the passing/failing tests. I need to determine if the different node between replaced between the two is what's causing the failure.

[bwitham]

There are two key differences in the new DuplicateWayRemover:

1) It is more strict in determining which ways are duplicates based on their tags (configurable). 2) It always merges name tags between duplicate ways, if all the other tags match.

The name tag merging in part 2) seems to be what's causing this problem, as leaving the code for 1) intact provides repeated consistent test results.

[bwitham]

The offending line of code is:

way2->setTags(tags2);

in DuplicateWayRemover::_updateWayNameTags

Disabling it prevents the test failures but, of course, yields incorrect DuplicateWayRemover test output.

[bwitham]

A little more progress...a little strange, but...

If I make a copy of way2 after updating it with the merged name tags and replace it on the map:

WayPtr way2Copy(new Way(*way2)); _map->replace(way2, way2Copy);

then TileConflatorTest passes consistently. However, then DuplicateWayRemoverTest fails and drops some ways completely from the output...not so good :-(

[bwitham]

The previously mentioned change really wasn't progress, b/c even though it made the hadoop test output consistent, it was consistently wrong output...seen in the missing ways in the DuplicateWayRemover output. Now, I need to isolate the section of the hadoop conflate code which causes the inconsistent conflate output when the new DuplicateWayRemover name tag merging is enabled.

[bwitham]

Disabling the LargeWaySplitter being applied by the LocalTileWorker ends the intermittent test failures in LocalTileWorkerTest...looking more closely at LargeWaySplitter...

[bwitham]

tile-conflator-out-54-fail-4.txt tile-conflator-out-54-pass-4.txt

[bwitham]

@jasonsurratt I might have to get some help from you, if you have the time...pulling my hair out over this one. Spent the last two days debugging, and I know roughly the lines of code causing the intermittent test failures, but not exactly why the failures are occurring. I haven't been able to find any uninitialized variables, use of qt uuid generation, and it looks like the same osm read/write code is used throughout the hadoop conflate code, which should make the node numbering consistent. Below is a summary of what I know using the latest code in the 54 branch.

For TileConflatorTest (running with repeatable uuid's and no optimizer time limit):

• If I comment out the name tag merging in line 191 of DuplicateWayRemover, I get consistent test output. Incorrect output, but consistent.
• If I comment out the large way splitting line 97 of LocalTileWorker, I get consistent test output. Incorrect output, but consistent.
• Test program log output for a passing and a failing test attached. A lot of debug logging was added, but the program output is identical between the two tests. On Friday, I did see some test output where the only difference between a passing and failing test was a differing node ID in the code that replaces node in relations, but that difference is not seen in the attached output.
• This may be irrelevant, but its strange enough to at least note. After adding debug logging to DuplicateWayRemover and LargeWaySplitter, somehow when running in debug mode I can get TileConflatorTest to pass every time (15 times in a row was as far as I went). Removing even just one debug log statement and then the test goes back to having intermittent failures...this is very strange to me, but there has to be a logical explanation.

thanks

[jasonsurratt]

I'm reviewing #128 now, but I'll recreate this on my machine again and give you a call to walk through it.

For your viewing pleasure.

[bwitham]

:-) that's funny. thanks, I appreciate it.

[jasonsurratt]

Working to recreate now...

[jasonsurratt]

After chatting w/ Brandon here are some things to check:

• Uninitialized variable. \ Use memcheck in valgrind to help find them.
• configuration options may not be coming across -- check by printing values in LocalTileWorker (like the consistent uuid value).
• LocalTileWorker is using QUuid -- change it.
• Look for entry lists for unsorted files
• Look for HDFS unsorted file lists

[bwitham]

Have tried every idea except valgrind with no success, so moving onto trying it out now. Even though the changes I've made so far haven't fixed the two failing tests, I think they're good changes to eventually merge in from the 54 branch, though.

[bwitham]

@jasonsurratt Officially (temporarily?) admitting defeat on this one. I made several changes related to the items on the brainstorm list, but none fixed the intermittently failing tests. I did think the code changes I made were positive ones, so pushed them to the remote branch anyway.

I ran valgrind on TileConflatorTest (will add some brief instructions for that to redmine when its back up). It found no uninitialized variables....I was able to find some, however, by using some new compiler switches and corrected them in the code. valgrind did report a bunch of false positive memory leaks, almost entirely focused on third party library code. I went through the whole list of them, and none in our code seemed legitimate to me. I wasn't able to run valgrind on HadoopTileWorkerTest, due to some environment var issues (didn't look much into making it work).

A long shot, but I also briefly played around with changing member variables in code related to the tests to be initialized, rather than assigned in the constructor, but that had no effect (found those with -Weffc++). Did not keep any of those changes.

[bwitham]

Possibly not a useful piece of information...but will note anyway.. if DuplicateWayRemover is moved later in the cleaning process for MapCleaner, the tests will pass consistently. However, that's not an appropriate solution to the problem.

[bwitham]

Unassigning this for now, due to intermittent test failure difficulties. May revisit later.

[jasonsurratt]

I'm running valgrind on TileConflatorTest now to have a look at the logs. I doubt I'll see anything different, but after that runs I'll start poking around a little deeper.

[bwitham]

thanks

[jasonsurratt]

I modified the LocalTileWorker to not delete the work as it proceeds and was able to see that the place where differences are occurring are after the third pass of the four pass conflation. This should narrow it down a bit. I'll keep digging.

[jasonsurratt]

I narrowed it down to the inconsistency occurring in LocalTileWorking during the call to _conflate. (~line 150) The map is consistent before the call and inconsistent after. This at least eliminates the loading operations (e.g. QDir calls and such).

[jasonsurratt]

Found a couple of places in the Conflator class where the shared pointers were being used to index sets. These were temporary and didn't appear to impact program flow at first, but then I realized that if the scores were identical then the ordering could impact flow. I changed the comparator to use score instead of the shared pointer and that changed the ordering of the output, but the files were otherwise identical (hoot score gave scores of exactly 1000 on all counts). This would explain why adding/removing print statements changed the output in your previous runs.

I'm rerunning it now with some extra memory churn added just in case. It has run several dozen times w/o issue. I'll let it run a few hundred times tonight and see what happens.

[jasonsurratt]

I ran a half dozen or so iterations w/ HadoopConflateTest and over 400 with the TileConflatorTest. It all checks out and commit was pushed. I will wait for Brandon's check before I merge this.

[bwitham]

@jasonsurratt Awesome! thanks. Those test each pass for me now, ten times in a row...never more than 2 in a row before. Let's merge it.

[bwitham]

The point of this task is to make duplicate way cleaning by default merge ways which are identical in every aspect except their name (duplicate.way.remover.strict.tag.matching=true), but also allow for a less strict situation where they can be merged if they are geometrically identical but have differing tags (duplicate.way.remover.strict.tag.matching=false).

TO TEST THIS (need to come with a better example than this):

• Open test-files/DcTigerRoads.osm in JOSM. Middle click the section of Constitution Ave in the previously attached pic to see that there are two roads on top of each other: Constitution Ave and US Hwy 50.
• The non-name tags for the two roads are identical for the two. Running the below command should result in the two roads being merged with one road's name being preserved in the alt_name tag since the strict tag matching is turned on:

hoot convert -D duplicate.way.remover.strict.tag.matching=true -D convert.ops=hoot::DuplicateWayRemover test-files/DcTigerRoads.osm tmp/DcTigerRoads-54-way-remove-strict-tag-matching-on.osm

The fact that the two ways merged together is no different than before this change was made, but the preservation of one of the names in the alt_name tag is a new to benefit related to this change.

• Copy DcTigerRoads.osm to DcTigerRoadsTemp.osm and: * to the single way with name="Constitution Ave NW", add the tag k="email" v="blah" * b. to all ways with name="US Hwy 50", add the tag k="email" v="blah2"
• Run:

hoot convert -D duplicate.way.remover.strict.tag.matching=true -D convert.ops=hoot::DuplicateWayRemover test-files/DcTigerRoadsTemp.osm tmp/DcTigerRoads-54-way-remove-strict-tag-matching-on-2.osm

The two ways should not merge now, since they have tags which contradict each other.

• Run:

hoot convert -D duplicate.way.remover.strict.tag.matching=false -D convert.ops=hoot::DuplicateWayRemover test-files/DcTigerRoadsTemp.osm tmp/DcTigerRoads-54-way-remove-strict-tag-matching-off.osm

The ways will merge, even though they have contradictory tags, since the strict tag matching was turned off.

[drew-bower]

Probably the longest hoot github issue to date. Nice work guys!

[jasonsurratt]

Ahhh...

[bwitham]

Forgot that I actually put test instructions in this....a couple comments up

[mikejeffe]

tested the DcTigerRoads.osm use case above and it matches expected behavior.