Yet another parser

[Tristram Gräbener-2]

Hello,

Parsing OSM has always be a problem. There are many tools with
excellent parsers but it's always complicated if you want a simple
format for your own specific routing project.
I tried to make a tool to parse relatively big areas and produce some
easy to use format (for now csv files and postgis base).

Of course it's far from being perfect and I could use some feedback ;)

The output is meant to be easy to use. Not a high perf format for
routing on a embended device or for real time drawing.

A tarball can be found at
http://cloud.github.com/downloads/Tristramg/osm4routing/osm4routing_v0.0.tar.gz
However, it seems to work randomly.
You can get the code with git: git clone
git://github.com/Tristramg/osm4routing.git

And report any problem/desire at
http://github.com/Tristramg/osm4routing/issues

Thank you for your attention :p

_______________________________________________
Routing mailing list
Routing@...
http://lists.openstreetmap.org/listinfo/routing

[Marc Coevoet-3]

Tristram Gräbener schreef:
> Hello,
>
> Parsing OSM has always be a problem. There are many tools with
> excellent parsers but it's always complicated if you want a simple
> format for your own specific routing project.
> I tried to make a tool to parse relatively big areas and produce some
> easy to use format (for now csv files and postgis base).
>
>  

I've always asked myself why we wouldn't try some quadtree algoritm for
parsing/routing/filing our data...


a very nice link:
http://www.geog.ubc.ca/courses/klink/gis.notes/ncgia/u37.html  (a
Belgian in Canada)

wiki
http://en.wikipedia.org/wiki/Quadtree

We've been discussing quadtrees at the VUB.ac.be in the years 1987 and
further.

The day we heard that the IGN data would become "protected", and we
weren't able to use it, we had a reason to be unhappy...

Marc

--
Shortwave transmissions in English, Francais, Deutsch, Suid-Afrikaans, Urdu, Cantonese, Greek, Spanish, Portuguese, ...
http://users.fulladsl.be/spb13810/radio/swlist/   
Stations list: http://users.fulladsl.be/spb13810/radio/txlist/


_______________________________________________
Routing mailing list
Routing@...
http://lists.openstreetmap.org/listinfo/routing

[Tristram Gräbener-2]

> I've always asked myself why we wouldn't try some quadtree algoritm for
> parsing/routing/filing our data...

As far as I understand quad-trees are useful if you want a fast query
to find you data.

However I wanted mainly a basic node-edges structure for those who
would like to play with routing algorithms (let's imagine a student
learning graph theory and who would like to try them on real data).
Personnaly, I just load all the data in memory so I have no access
speed problem (France is only 1M edges big).

If you want some spatial queries, postgis (using GIST-indexes) works
pretty well.
For a more portable app (let's say a desktop app), sqlite has a R-tree support.

Of course if you have a specific idea in mind (routing over very big
regions with little memory), then I don't know :)

> The day we heard that the IGN data would become "protected", and we
> weren't able to use it, we had a reason to be unhappy...

Well, now we have OSM ;)

_______________________________________________
Routing mailing list
Routing@...
http://lists.openstreetmap.org/listinfo/routing

[Dennis Luxen]

> I've always asked myself why we wouldn't try some quadtree algoritm  
> for
> parsing/routing/filing our data...

Well, Quad-Trees don't help you much when it comes to routing. It's a  
data structure that helps answering queries that ask for a nearest  
neighbor to some coordinate. For routing it is the easiest to use a  
simple adjancy list representation for the graph. And when it comes to  
a serious routing scenario, where you have millions of edges and nodes  
then you need to do specialized preprocessing. Dijkstras classical  
algorithm and related heuristics don't scale that well on large data  
sets. There are several exact speedup-techniques for that problem.

Again, a Quadtree is an index structure that answers neighborhood  
queries fast like "Whats the nearest neighbor to coordinate xy?" or  
"What is all information we have for a certain region or tile?".  
Routing on the other hand implies some connection between the nodes  
that is easier (meaning: more efficiently) to exploit than a spatial  
index. On the other hand, I have to acknowledge that there is  
scientific work, that speeds up Dijkstras algorithm by employing tree-
like data structures but only among other algorithmic techniques.

> We've been discussing quadtrees at the VUB.ac.be in the years 1987 and
> further.

And they are still in use in many applications.

--Dennis


_______________________________________________
Routing mailing list
Routing@...
http://lists.openstreetmap.org/listinfo/routing

[Marcus Wolschon - Wolschon Softwaredesign]

On Tue, 3 Nov 2009 08:20:54 +0100, Dennis Luxen <luxen@...> wrote:
>> I've always asked myself why we wouldn't try some quadtree algoritm  
>> for
>> parsing/routing/filing our data...
>
> Well, Quad-Trees don't help you much when it comes to routing. It's a  
> data structure that helps answering queries that ask for a nearest  
> neighbor to some coordinate. For routing it is the easiest to use a  
> simple adjancy list representation for the graph.

Actually it does.
Because before you can do the actual routing you have to find
the nearest Street the driver can actually be on and you have
to find all the target-locations.
For navigation as opposed to route-finding you also need
to continously render a moving map and for that you need
to answer range-queries VERY fast.
This part is actually more demanding on the datastructures
used then simply getting all ways a node is connected to,
the next+prev node along a way and some tags on the ways/nodes
you are evaluating in your routing-application. Also because
the rendering is a realtime-case while route-calculation  happens
usually only once.


> And when it comes to  
> a serious routing scenario, where you have millions of edges and nodes  
> then you need to do specialized preprocessing. Dijkstras classical  
> algorithm and related heuristics don't scale that well on large data  
> sets. There are several exact speedup-techniques for that problem.

Can you please point out a few and maybe even add links to them on
the "Routine" wiki-page? This may be interesting for a lot
of readers.

> Again, a Quadtree is an index structure that answers neighborhood  
> queries fast like "Whats the nearest neighbor to coordinate xy?" or  
> "What is all information we have for a certain region or tile?".

As I pointed out. Very usefull. It need not be the only index.

> Routing on the other hand implies some connection between the nodes  
> that is easier (meaning: more efficiently) to exploit than a spatial  
> index. On the other hand, I have to acknowledge that there is  
> scientific work, that speeds up Dijkstras algorithm by employing tree-
> like data structures but only among other algorithmic techniques.

(Another index by ID and a backward-reference from node to way
and from node/way/relation to relation are a very, very good thing
for the route-calculation.)

Marcus

_______________________________________________
Routing mailing list
Routing@...
http://lists.openstreetmap.org/listinfo/routing

[Marc Coevoet-3]

Dennis Luxen schreef:
>> I've always asked myself why we wouldn't try some quadtree algoritm  
>> for
>> parsing/routing/filing our data...
>>    
>
> Well, Quad-Trees don't help you much when it comes to routing. It's a  
> data structure that helps answering queries that ask for a nearest  
> neighbor to some coordinate.

They use quadtrees at google (for display), I do not know if it is for
routing, but.. (if they use quadtrees at google, it is a reason not to
study quadtrees here ;-)  "I am a shareholder "...

I have the idea routing algos sometimes take too much roads of no
importance, and arrive where the traffic shouldn't come.

if you organise a hierarchy of roads, say highways, then "route
nationale", then "departementale", you can always prefer to take
highways instead of nationales, etc, for a LONG journey.  And I guess
there is a relation between "hierarchy" and "dichotomy" somewhere.  
Where do they meet ??

Marc

--
What's on Shortwave guide: choose an hour, go!
http://whatsonshortwave.tk
700+ Radio Stations on SW http://swstations.tk
300+ languages on SW http://radiolanguages.tk


_______________________________________________
Routing mailing list
Routing@...
http://lists.openstreetmap.org/listinfo/routing

[Marcus Wolschon - Wolschon Softwaredesign]

On Tue, 03 Nov 2009 12:00:03 +0100, Marc Coevoet <sintsixtus@...>
wrote:

> Dennis Luxen schreef:
>>> I've always asked myself why we wouldn't try some quadtree algoritm  
>>> for
>>> parsing/routing/filing our data...
>>>    
>>
>> Well, Quad-Trees don't help you much when it comes to routing. It's a  
>> data structure that helps answering queries that ask for a nearest  
>> neighbor to some coordinate.
>
> They use quadtrees at google (for display), I do not know if it is for
> routing, but.. (if they use quadtrees at google, it is a reason not to
> study quadtrees here ;-)  "I am a shareholder "...

They use something very different for routing.
An aproach based on map-reduce that works very well
for their scale but does not scale down to anything below
1 datacenter. ;)

> I have the idea routing algos sometimes take too much roads of no
> importance, and arrive where the traffic shouldn't come.

what routers with what routing-algorithms, target-metric
and parameters did you use?

the shortest route for example will almost always
use roads of low importance as anything else will just
not be the shortest route.

> if you organise a hierarchy of roads, say highways, then "route
> nationale", then "departementale", you can always prefer to take
> highways instead of nationales, etc, for a LONG journey.  And I guess
> there is a relation between "hierarchy" and "dichotomy" somewhere.  
> Where do they meet ??

I have no idea what a "route nationale" and "departementale" are but
we already have a hirachy expressed via the "highway"-tag.


Marcus

_______________________________________________
Routing mailing list
Routing@...
http://lists.openstreetmap.org/listinfo/routing

[Dennis Luxen]

> For navigation as opposed to route-finding you also need
> to continously render a moving map and for that you need
> to answer range-queries VERY fast.

Yes, but that is rendering. I was speaking about finding a route between
two nodes in a strongly connected graph.

> Can you please point out a few and maybe even add links to them on
> the "Routine" wiki-page? This may be interesting for a lot
> of readers.

Just google "speedup-technique dijkstra".

--Dennis

_______________________________________________
Routing mailing list
Routing@...
http://lists.openstreetmap.org/listinfo/routing

[Dennis Luxen]

> if you organise a hierarchy of roads, say highways, then "route
> nationale", then "departementale", you can always prefer to take
> highways instead of nationales, etc, for a LONG journey.  And I guess
> there is a relation between "hierarchy" and "dichotomy" somewhere.  
> Where do they meet ??

This idea is actually a very common heuristic to find paths. There are
several commercial vendors that do their route planning that way. First,
find a nearby highway from the origin, then get as close as possible to
the destination and from there find your way "somehow" to the
destination. For those of you who have experienced bad routes with a
commercial navigation device, this is most probably the reason for it.
Exact routing in the sense of shortest = best routes is not easy to
computed on an onboard unit because of speed and memory limitations.

In some cases, the above routing scheme might work reasonable, but this
not exact at all. When looking at shortest paths, routes can be
arbitrarily wrong with this routing scheme. Although, there is also an
exact routing algorithm called "Highway Hierarchies", which is exact and
computes a hierarchy of streets on its own.

You can find many scientific publications on the subject at the
following website:
https://algo2.iti.uni-karlsruhe.de/english/publications.php

I'd suggest to look at "Contraction Hierarchies".

-Dennis

_______________________________________________
Routing mailing list
Routing@...
http://lists.openstreetmap.org/listinfo/routing

[Lambertus]

Dennis Luxen wrote:

>> if you organise a hierarchy of roads, say highways, then "route
>> nationale", then "departementale", you can always prefer to take
>> highways instead of nationales, etc, for a LONG journey.  And I guess
>> there is a relation between "hierarchy" and "dichotomy" somewhere.  
>> Where do they meet ??
>
> This idea is actually a very common heuristic to find paths. There are
> several commercial vendors that do their route planning that way. First,
> find a nearby highway from the origin, then get as close as possible to
> the destination and from there find your way "somehow" to the
> destination. For those of you who have experienced bad routes with a
> commercial navigation device, this is most probably the reason for it.
> Exact routing in the sense of shortest = best routes is not easy to
> computed on an onboard unit because of speed and memory limitations.
>
> In some cases, the above routing scheme might work reasonable, but this
> not exact at all. When looking at shortest paths, routes can be
> arbitrarily wrong with this routing scheme. Although, there is also an
> exact routing algorithm called "Highway Hierarchies", which is exact and
> computes a hierarchy of streets on its own.
>
> You can find many scientific publications on the subject at the
> following website:
> https://algo2.iti.uni-karlsruhe.de/english/publications.php
>
> I'd suggest to look at "Contraction Hierarchies".
>
> -Dennis
>

I've done a few tests with the online demo of their contraction
hierarchies routing engine and the results are astonishing: South- to
North- Germany in 65 milliseconds. Very impressive. But I don't know how
many parameters are considered on each edge (turn restrictions, traffic
lights, sharp corners etc).

It would be awesome if this routing engine could be tested with OSM
data. I.e. how much disk space, preprocessing time and memory needed for
generating a routing database containing the whole OSM database, and
also how these parameters look like when doing routing calculations on
that database.

_______________________________________________
Routing mailing list
Routing@...
http://lists.openstreetmap.org/listinfo/routing

[Dennis Luxen]

> I've done a few tests with the online demo of their contraction
> hierarchies routing engine and the results are astonishing: South- to
> North- Germany in 65 milliseconds. Very impressive. But I don't know how
> many parameters are considered on each edge (turn restrictions, traffic
> lights, sharp corners etc).

Did you try that one ?
http://algo2.iti.kit.edu/schultes/hwy/demo/applet.html

As far as I know, the online demo is running the Highway Hierarchies
algorithm. But still, most of the 65ms is used for communication. With
the current Contraction Hierarchy code it should be even less.

> It would be awesome if this routing engine could be tested with OSM
> data. I.e. how much disk space, preprocessing time and memory needed for
> generating a routing database containing the whole OSM database, and
> also how these parameters look like when doing routing calculations on
> that database.

I experimented on the road network of Germany about a year ago.
Preprocessing was something like 5 mins or so. Have a look at the
Contraction Hierarchies paper at
https://algo2.iti.uni-karlsruhe.de/routeplanning.php

It states the times for commercial european and north american road
networks that are more dense than the osm data.

--Dennis

_______________________________________________
Routing mailing list
Routing@...
http://lists.openstreetmap.org/listinfo/routing

[Dennis Luxen]

> They use something very different for routing.

Then what is their algorithm?

> An aproach based on map-reduce that works very well
> for their scale but does not scale down to anything below
> 1 datacenter. ;)

I wouldn't bet on Google not knowing the latest research.

>> I have the idea routing algos sometimes take too much roads of no
>> importance, and arrive where the traffic shouldn't come.
>
> what routers with what routing-algorithms, target-metric
> and parameters did you use?
>
> the shortest route for example will almost always
> use roads of low importance as anything else will just
> not be the shortest route.

Some would argue that the roads with highest importance tend to lie on  
many shortest paths, i.e. the important highway was built for a  
reason. Or how do you define importance?

--Dennis

_______________________________________________
Routing mailing list
Routing@...
http://lists.openstreetmap.org/listinfo/routing

[Tristram Gräbener-2]

>> They use something very different for routing.
>
> Then what is their algorithm?
There a good chances that they use an approach similar to that one :

Precomputation:
- Find 100 × 100 points in europe (that means a point every 30km)
- Compute the distance between all those points and store it

On request:
- compute the shortest path to the nearest pre-computed node (dijkstra
on a 30 by 30 km is not even a ms) on start and destination
- you get an extreamly good approximation
- use A* having this extra information.

If your A* algorithm knows the exact distance to the destination, then
it will run in O(n).

Of course you can hack as much as you want arround that to improve the
performances, but you get the idea.

Finding the fastest route in less than a second in a desktop computer,
is an easy task.

The problem is finding a good route: avoiding to many changes, taking
in account traffic lights, speed differences and so on.
The other problem is on small devices with little memory (displaying
the map is yet an other problem...)

> Some would argue that the roads with highest importance tend to lie on
> many shortest paths, i.e. the important highway was built for a
> reason. Or how do you define importance?

The problem is that we want a combination of shortest, fastest and
most confortable route.
The shortest we have the data. The fastest, we would need more data.
The most confortable depends on every one. No real solution there.

_______________________________________________
Routing mailing list
Routing@...
http://lists.openstreetmap.org/listinfo/routing

[Marcus Wolschon - Wolschon Softwaredesign]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Dennis Luxen schrieb:
>> They use something very different for routing.
> Then what is their algorithm?

I reat a paper on it. Quite interesting.
Basically precomputing lots of routes
with a lot of simplifying.

>> An aproach based on map-reduce that works very well for their
>> scale but does not scale down to anything below 1 datacenter. ;)
>
> I wouldn't bet on Google not knowing the latest research.
Why do you think so?
They have to scale UP to hundrets of
datacenters. Their code never has to scale
DOWN to run on a mobile phone or a single
pc for that  matter.

>>> I have the idea routing algos sometimes take too much roads of
>>> no importance, and arrive where the traffic shouldn't come.
>> what routers with what routing-algorithms, target-metric and
>> parameters did you use?
>>
>> the shortest route for example will almost always use roads of
>> low importance as anything else will just not be the shortest
>> route.
>
> Some would argue that the roads with highest importance tend to lie
> on many shortest paths, i.e. the important highway was built for a
>  reason. Or how do you define importance?

That many people drive from A to B does not mean
that you want to take their road when driving from C to D .
Also roads are build for political reasons, different
distribution of money between comunities, geographical
difficulties, historic reasons...
nothing of this has anything to do with you route at this
day and optimized for what kind of route you want this time.

Marcus

>
> --Dennis
>
> _______________________________________________ Routing mailing
> list Routing@...
> http://lists.openstreetmap.org/listinfo/routing

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iEYEARECAAYFAkrwfmoACgkQf1hPnk3Z0cRhYACgu2U0RcJbzoLNsGuBIVVAEA/N
+L8An0tau3u1hPnY+gpPaM7qPWOOpFkQ
=SfNL
-----END PGP SIGNATURE-----


_______________________________________________
Routing mailing list
Routing@...
http://lists.openstreetmap.org/listinfo/routing

[Marc Coevoet-3]

Tristram Gräbener schreef:

>>> They use something very different for routing.
>>>      
>> Then what is their algorithm?
>>    
> There a good chances that they use an approach similar to that one :
>
> Precomputation:
> - Find 100 × 100 points in europe (that means a point every 30km)
> - Compute the distance between all those points and store it
>
>  

Every 30km?  Choose a popular location close to it ..

You know what a transition matrix is??  Product of transition matrix??

The Nth product will give you all paths of lenth N ;-)  (close subject:
markov chains)

In modern times 100.000 destinations isn't that much ;-)
100.000 x 100.000 matrix.

I made fractals that were about 23500x23500 pixels and I didn't find a
print shop where they could print decently ;-)
only 2gb ram@home
This black white image can be seen as a trans matrix with 23500
locations. (allocated must have been 32 bits for 1 pixel black or white)


Marc


--
What's on Shortwave guide: choose an hour, go!
http://whatsonshortwave.tk
700+ Radio Stations on SW http://swstations.tk
300+ languages on SW http://radiolanguages.tk


_______________________________________________
Routing mailing list
Routing@...
http://lists.openstreetmap.org/listinfo/routing

[Tristram Gräbener-2]

>> There a good chances that they use an approach similar to that one :
>>
>> Precomputation:
>> - Find 100 × 100 points in europe (that means a point every 30km)
>> - Compute the distance between all those points and store it
>>
>>
> Every 30km?  Choose a popular location close to it ..
Not really necessary, as anyway you will compute the shortest path to
that point. The goal is only to have a very good distance estimation.
Not the path itself.
Of course being smart while choosing the points will turn out in a
slightly faster solution. Not really a big deal.

And even choosing a 1000×1000grid (a node every 3km) will only consume
4 Mb (you just store a duration for every pair  of start-destination).
But you will need to run one million times a shortest path algorithm
in before hand.

> You know what a transition matrix is??  Product of transition matrix??
> The Nth product will give you all paths of lenth N ;-)  (close subject:
> markov chains)
The matrix will contain all 100^2 distances. It's not an adjacency matrix.
So you won't compute the paths using the matrix, but a plain old A*.

> In modern times 100.000 destinations isn't that much ;-)
> 100.000 x 100.000 matrix.
Again, you don't pre-compute the paths. You just pre-compute a few
distances in order to have a better heuristic and achieve a
quasi-linear shortestpath algorithm.
You'll have as many destinations as you have nodes in your graph
(about 1 million currently in OSM for France).

_______________________________________________
Routing mailing list
Routing@...
http://lists.openstreetmap.org/listinfo/routing

[Marc Coevoet-3]

Tristram Gräbener schreef:

>>> There a good chances that they use an approach similar to that one :
>>>
>>> Precomputation:
>>> - Find 100 × 100 points in europe (that means a point every 30km)
>>> - Compute the distance between all those points and store it
>>>
>>>
>>>      
>> Every 30km?  Choose a popular location close to it ..
>>    
> Not really necessary, as anyway you will compute the shortest path to
> that point. The goal is only to have a very good distance estimation.
> Not the path itself.
> Of course being smart while choosing the points will turn out in a
> slightly faster solution. Not really a big deal.
>
> And even choosing a 1000×1000grid (a node every 3km) will only consume
> 4 Mb (you just store a duration for every pair  of start-destination).
> But you will need to run one million times a shortest path algorithm
> in before hand.
>
>  

This is a variant of distcc or distmp3 (in debian/ubuntu the pkg are
called so).



Marc


--
What's on Shortwave guide: choose an hour, go!
http://whatsonshortwave.tk
700+ Radio Stations on SW http://swstations.tk
300+ languages on SW http://radiolanguages.tk


_______________________________________________
Routing mailing list
Routing@...
http://lists.openstreetmap.org/listinfo/routing

[Dennis Luxen]

Tristram Gräbener schrieb:
>>> They use something very different for routing.
>> Then what is their algorithm?
> There a good chances that they use an approach similar to that one :

[A*/Reach/Real variants snipped]

I don't think so. A* and related algorithms are too slow for large road
networks of entire continents. Even hacking doesn't help to overcome
that performance barrier. And still A* is a heuristic algorithm. It can
perform arbitrarily bad. And correct me if I'm wrong, but didn't the
algorithm you describe come from MS Research? That would be another
reason for Google not to use it.

_______________________________________________
Routing mailing list
Routing@...
http://lists.openstreetmap.org/listinfo/routing

[Dennis Luxen]

> I reat a paper on it. Quite interesting.
> Basically precomputing lots of routes
> with a lot of simplifying.

I'd suggest to read it again if you mean the Contraction Hierachies
paper. The method is based on node contraction. That means it is
inserting so-called shortcuts into the graph. Nodes are deleted from the
graph and new edges are inserted that shortcut the deleted node. Routes
are computed only to verify if a shortcut is necessary. No precomputed
paths are stored.

-Dennis


_______________________________________________
Routing mailing list
Routing@...
http://lists.openstreetmap.org/listinfo/routing

[Tristram Gräbener-2]

> I don't think so. A* and related algorithms are too slow for large road
> networks of entire continents. Even hacking doesn't help to overcome
> that performance barrier. And still A* is a heuristic algorithm. It can
> perform arbitrarily bad. And correct me if I'm wrong, but didn't the
> algorithm you describe come from MS Research? That would be another
> reason for Google not to use it.

The approach I described seems to be a common base to compute the
shortest path. Then you can hack arround as much as you want.

The performances of A* strongly depends on the heuristic.
If you have THE perfect heuristic that knows exactly the smallest
*distance* to the destination, then the A* will iterate only the nodes
of the shortest path. As anyway you will have to list those nodes at
some point (to render the path for example), it's impossible to have a
better algorithm. If you have the shortest path stored somewhere, then
improvement would be better only by a constant factor.

That approch tries to get an almost perfect estimation of the distance
to the destination and it's quite hard to trick.

The europe OSM map has arround 10M nodes I guess (in the node-edge
sense, not in the OSM sense). I only I weren't that lasy to implement
it to have a better idea of how it really performs...

_______________________________________________
Routing mailing list
Routing@...
http://lists.openstreetmap.org/listinfo/routing