Opened 5 years ago

Closed 4 years ago

#1177 closed defect/bug (fixed)

Search does not find interpolated house numbers from OSM

Reported by: sleske Owned by:
Priority: major Milestone: version 0.5.1
Component: mapdrivers/OSM Version: git master
Severity: complex Keywords: housenumber, interpolation, ipo, address
Cc:

Description

When using data from OpenStreetMap?, Navit's search does not find interpolated house numbers (numbers indicated by a way with tag addr:interpolation).

Example:

House number 23 of Gottfried-Daniels-Straße, Köln, Germany.

OSM data has an interpolation for numbers 9 to 37: http://www.openstreetmap.org/browse/way/40900757 . Nominatim will therefore find the address: http://nominatim.openstreetmap.org/details.php?place_id=100655812

If I search for Gottfried-Daniels-Straße, Köln in Navit's search dialog (internal GUI / Town) and start the housenumber search, typing "2" only offers numbers 2 and 24.

This is with SVN rev. 5654, and a binfile map from http://maps.navit-project.org/ from early October 2013.

Change History (13)

comment:1 Changed 5 years ago by sleske

Oddly enough, there seems to be code in Navit for handling interpolated house numbers (in maptool/osm.c, in map/binfile/binfile.c, in search.c...). There are also several commits which mention house number interpolation.

However, I can't figure out how to get it to work...

comment:2 Changed 5 years ago by usul

  • Keywords housenumber interpolation ipo address added
  • Severity set to complex

comment:3 Changed 5 years ago by usul

  • Milestone changed from version 0.6.0 to version 0.5.1

As this is a malfunctions of (somewhat) existing feature, I recommend to solve this issue already in next hotfix release

comment:4 follow-up: Changed 5 years ago by tryagain

Actually, we have some code for address interpolation, including recent additions by cp15.

Something made me think I have even seen address interpolation to be working. I definitely made a few attempts to test it, but cant recall results for now.

But... Reviewing actual code contents, it looks like current address interpolation code is not connected with binfile data provided by maptool.

Address interpolation code depends on attr_house_number_left*, attr_house_number_right* attributes, but maptool does not even attempt to generate them. I think this code, if it would be written, will do another maptool pass connecting all housenumbers with all interpolation ways, which will cost O(N(house number nodes)xN(interpolation=* ways)), which I estimate to 1-2 hours of runtime on planet. I think it's quite slow.

Another way to implement address interpolation would be to keep maptool code as is, but attempt to do above union during address search. Would require to hold in memory all house numbers for the given street search area and all addr_intepolation way items. Seems to be doable. I even think I have seen similar code in our sources before, but cant find it now. Can't it have been removed as dead code?

comment:5 Changed 5 years ago by sleske

Thanks a lot for the information. I will look at the code (and the SVN logs) again with this in mind. Maybe I can find a solution.

comment:6 Changed 5 years ago by sleske

comment:7 in reply to: ↑ 4 ; follow-up: Changed 5 years ago by sleske

Replying to http://wiki.navit-project.org/index.php/user:tryagain:

Actually, we have some code for address interpolation, including recent additions by cp15.

[...]

Address interpolation code depends on attr_house_number_left*, attr_house_number_right* attributes, but maptool does not even attempt to generate them. I think this code, if it would be written, will do another maptool pass connecting all housenumbers with all interpolation ways, which will cost O(N(house number nodes)xN(interpolation=* ways)), which I estimate to 1-2 hours of runtime on planet. I think it's quite slow.

Yes, I am planning to go in this direction, by transferring the housenumber information from the end nodes to the interpolation ways. However, I don't think this will need an extra pass.

I saw in the code that the nodes are already stored in a hash map to resolve the ways that they are part of; maybe we can store the address information there, too. I'll see...

comment:8 in reply to: ↑ 7 ; follow-up: Changed 5 years ago by tryagain

Replying to sebastian leske:

I saw in the code that the nodes are already stored in a hash map to resolve the ways that they are part of; maybe we can store the address information there, too. I'll see...

There's only node ID and coordinates are stored in that data structure. BTW, hash is used only if nodes come out of order. Processing planet.osm, we use binary search in ordered array to find node by id, not hash.

All attributes are stripped from the nodes before we put them there. Even this way we're unable to store all nodes in memory at once so we do several passes, splitting all data into slices. For the whole planet, this node id+coordinate list is 36Gb long, so we split it into 14 2.5Gb slices. Slice size depends on our server hw capabilities and its load by other tasks.

comment:9 in reply to: ↑ 8 Changed 5 years ago by sleske

Replying to http://wiki.navit-project.org/index.php/user:tryagain:

There's only node ID and coordinates are stored in that data structure. BTW, hash is used only if nodes come out of order. Processing planet.osm, we use binary search in ordered array to find node by id, not hash.

Thank you for the information. I'll try to find a way to store the housenumber information along with the nodes. I suppose I'll have to allocate additional data structures for this.

All attributes are stripped from the nodes before we put them there. Even this way we're unable to store all nodes in memory at once so we do several passes, splitting all data into slices. For the whole planet, this node id+coordinate list is 36Gb long, so we split it into 14 2.5Gb slices. Slice size depends on our server hw capabilities and its load by other tasks.

I realize I'll have to pay attention to memory usage. Still, there's not that much interpolation information in OSM, so I hope it will not cost too much memory.

comment:10 Changed 4 years ago by sleske

It took me a while to become familiar with maptool, but I have managed to add processing of addr:interpolation to maptool. The new code is very similar to the processing of "associatedStreet" relations, as proposed by tryagain, and basically treats interpolation ways as relations.

I'll have to test and clean up the code a bit, but hope to commit it shortly. I have already committed some refactorings I did in preparation.

I have done some performance tests with the new maptool: Memory usage is not increased significantly - it's just an extra pass, and each pass frees its memory at the end. It does add an extra pass over all nodes & ways, so processing will take longer. In my tests the runtime only increased by 5-10%, but that was with small files - for large files the slowdown may be greater, because I/O caching becomes less effective.

At any rate, thanks a lot to tryagain for the advice on how to implement this!

comment:11 follow-up: Changed 4 years ago by tryagain

sleske, i'm happy to read this. Would be quite a useful feature to have this working.

But can you please revert that --experimental switch removal. We sometimes do activate this code to make our server build another map and let willing people to test some experimental features.

For an example, see http://sourceforge.net/p/navit/code/5491/ http://sourceforge.net/p/navit/code/5639/ http://sourceforge.net/p/navit/code/5644/ and http://sourceforge.net/p/navit/code/5780/log/?path=/trunk/navit/navit/maptool/maptool.c in general.

comment:12 in reply to: ↑ 11 Changed 4 years ago by sleske

Replying to https://wiki.navit-project.org/index.php/user:tryagain:

But can you please revert that --experimental switch removal. We sometimes do activate this code to make our server build another map and let willing people to test some experimental features.

Ok, I didn't know that - it just looked like dead code. I put it back with r5792. I also added a description string (to be filled in), to print a description of the experimental features.

comment:13 Changed 4 years ago by sleske

  • Resolution set to fixed
  • Status changed from new to closed

It's taken me a while, but it's done now :-). I just committed support for OSM house number interpolation - r5805 and preceding commits.

I also did several refactorings, to remove redundancies and (hopefully) make the code easier to understand, and added comments.

Note about performance:

Since maptool has to do a bit more work now, maptool processing will take longer. I tested with an OSM extract for the region of Düsseldorf(Germany) - about 150MB of bzipped XML. On my (fairly old) computer, processing time increased from 221 to 249s, or about 13%. I hope this is acceptable even for processing the whole planet.

Note for testing:

I had to change both the search and maptool processing, so to use this feature, you will need both a fresh Navit and a binfile created with a fresh maptool.

Note: See TracTickets for help on using tickets.