Address Geocoding?
Preet
First, thanks for the quick reply to my earlier question. I have a few
more questions/comments regarding geocoding in MoNav. Right now it
seems like a hierarchical search is being used to convert named
locations into lat/lon coodinates for routing. I tried going through
the wiki to understand exactly how this works from the pulled OSM
data, but I'm not too clear on it. Could you explain how the search
works in layman's terms?
While the search is very fast, I think the City > Street method is a
bit limited. Specifically there's ambiguity about what city a
particular street belongs in because its subject to OSM's database. I
tried looking up my residence address, but I wasn't able to get the
city right. I had to go back to openstreetmap.org and find out which
City the OSM db 'thought' my street was in, and then use that. In an
ambiguous case though, the guess that the user puts in for the city is
likely to be geographically close to the actual city the street was
listed under with OSM's db. It might be worth searching the
neighbouring regions if no match is found.
I also wanted to ask whether or not there were any plans to bring the
geocoding ability of MoNav closer to something like Nominatim
currently accomplishes, specifically the ability to look up specific
addresses, postal codes and POIs. Adding this sort of feature set
would increase MoNav's usability substantially. I understand this
would be a major undertaking, but was curious whether or not there
were any such plans in MoNav's future.
Christian Vetter
On Thu, Jun 16, 2011 at 4:40 AM, Preet <preet...@gmail.com> wrote:
> Hiya,
>
> First, thanks for the quick reply to my earlier question. I have a few
> more questions/comments regarding geocoding in MoNav. Right now it
> seems like a hierarchical search is being used to convert named
> locations into lat/lon coodinates for routing. I tried going through
> the wiki to understand exactly how this works from the pulled OSM
> data, but I'm not too clear on it. Could you explain how the search
> works in layman's terms?
The address data is calculated from OSM data as follows:
1. Each node is assigned to a single city. If a city boundary polygon
is available it is used, otherwise every node within a given radius (
determined by city type ) is assigned to the city. Smaller cities
trump larger ones ( otherwise small villages near a large city would
be consumed by it ).
2. Each way is assigned to every city one of its nodes is in.
The address search then builds a hierarchical data structure for each
city ( containing all the city's streets ) as well as for the city
names themselves. This data structure allows for fast computation of
auto-completion entries ( only one disk read ).
Basically it is a trie [1] combined with a tournament tree [2]. The
trie allows us to find all entries starting with a given prefix and
the tournament tree allows us to extract the top k elements from this
set of entries. The advantage is very high speed on mobile devices.
The disadvantage is that we cannot correct typing errors and have to
search for a city first, then the street.
> While the search is very fast, I think the City > Street method is a
> bit limited. Specifically there's ambiguity about what city a
> particular street belongs in because its subject to OSM's database. I
> tried looking up my residence address, but I wasn't able to get the
> city right. I had to go back to openstreetmap.org and find out which
> City the OSM db 'thought' my street was in, and then use that. In an
> ambiguous case though, the guess that the user puts in for the city is
> likely to be geographically close to the actual city the street was
> listed under with OSM's db. It might be worth searching the
> neighbouring regions if no match is found.
A simple fix would be to add streets to several possible cities and
mark them as "foreign" candidates.
> I also wanted to ask whether or not there were any plans to bring the
> geocoding ability of MoNav closer to something like Nominatim
> currently accomplishes, specifically the ability to look up specific
> addresses, postal codes and POIs. Adding this sort of feature set
> would increase MoNav's usability substantially. I understand this
> would be a major undertaking, but was curious whether or not there
> were any such plans in MoNav's future.
There are definitely plans to improve upon the address search, however
it might take some time:
- We want to use the Karlsruher Address Schema [3] instead of the
radius heuristic. However, at the moment it does not cover most of the
data set. On the bright side we would be able to assign streets to the
correct city and get house number for many large cities.
- A reverse search ( first street, then city ) might also be easy to
add, depending on the demand for it
- POI search is definitely planned, but not through the address
search plugin. It makes more sense to group POIs into categories and
display every entry of a single category in the vicinity on the map.
- A free form address search ( somewhat akin to Nominatim, but more
resilient to typing mistakes ) would be possible to implement, but
might run slowly on mobile devices. We will do it eventually, but not
in the near future. If somebody is interested in doing this, I can
provide ample hints on how to do so ( e.g. [4] ). Also the author of
OSRM ( shares some code with MoNav ) is experienced in this area and
might implement [4] for OSRM, allowing us to just use it.
I hope this answers some of your questions. Feel free to write if you
are interested in some details.
Regards,
Christian Vetter
[1]: http://en.wikipedia.org/wiki/Radix_tree
[2]: http://en.wikipedia.org/wiki/Selection_algorithm#Tournament_Algorithm
[3]: http://wiki.openstreetmap.org/wiki/Proposed_features/House_numbers/Karlsruhe_Schema
[4]: http://algo2.iti.kit.edu/english/1533.php
Preet
Thanks for the detailed reply! I was going through the source code,
thinking that I might try to implement an Address plug-in with street
numbers and one that tries to resolve the street/city issue I
mentioned earlier. Unfortunately I got a bit lost when your code
refers to the files generated by the preprocessor for address lookup.
How would I go about accessing data from those preprocessor files?
Regards,
-Preet
> [4]:http://algo2.iti.kit.edu/english/1533.php
Christian Vetter
Basically you have to split your functionality in 2 ( maybe 3 ) parts.
The way MoNav works is like this:
Preprocessor:
The chosen importer plugin processes the input file and converts it to
some intermediate data format
Each plugin's preprocessor part requests data from the importer
plugin, processes it and stores it in its own format
The plugin's data is copied to the client's data directories
Client:
Each plugin can work with the data it has stored during preprocessing
This approach has some advantages:
- once the importer is able to parse specific data schemes it is
available to all plugin
- we can implement a new importer to support different data sources
- the plugin can apply complicated algorithms during the
preprocessing and store the data in a way that suites the client's
plugin best
Some disadvantages are:
- each plugin must store its own data, there is no reusing other plugins data
- you have to split functionality between the importer, preprocessor
plugin and client plugin ( could also be an advantage )
So the basic approach for implementing your own plugins would be:
1. See whether the current IImporter interface supports the data you
need. If not you have to modify it ( do not forget to increase
interface versions in that case )
2. See whether the current importer plugins support the data you need.
If not add functionality to parse this data, store it in an
intermediate format and retrieve it.
3. Implement a IPreprocessor plugin that requests the data from the
importer, converts it / computes stuff from it / ... and stores the
result in files to be used by the client's plugin
4. Implement a IAddressLookup / IRenderer / IRouter that works with
the data. It has to have the same name as the IPreprocessor plugin (
GetName() )
You could also modify existing plugins, if they suite you need.
To implement the functionality you mentioned ( fix city / street
association ) it is highly likely that is suffices to do some changes
to the OSMImporter plugin.Take a look at computeInCityFlags(), maybe
remapEdges() and GetAddressData(). That's were it's currently handled:
computeInCityFlags: this computes for each node whether it belongs to
one specific city and if it does to which.
remapEdges: Just the city flag data
GetAddressData: read the edges and generates address entries from them
I hope that helped a bit.
Best regards,
Christian Vetter