data (#23) - time of finding path (#389) - Message List

time of finding path

We have server Dell PowerEdge? 1850. We gon geberated base of Europe and Asia help of the tool osm2pgrouting. How much time take finding the path from Madrid to Moscow.

  • Message #1682

    First, you won't be able to use osm2pgrouting to import a very large area with lots of roads as yours will probably be.

    Second, it might take minutes to get a route from Madrid to Moscow, if you don't use a clever strategy how to load your data, and if your data is large. Such a strategy (like layering) depends very much on your use case.

    • Message #1736

      I have the same problem, I think, and also try to solve it. It seems like there is bottleneck in selection from ways table. I reduced total amount of ways in Europe and Russia to 4.2m using only ways of needed classes. Also I select only ways from area between points

      $delta = 1;
      $minLon = min($cityFrom['longitude'], $cityTo['longitude']);
      $maxLon = max($cityFrom['longitude'], $cityTo['longitude']);
      $minLat = min($cityFrom['latitude'], $cityTo['latitude']);
      $maxLat = max($cityFrom['latitude'], $cityTo['latitude']);
      $res = $conn->execute("
            SELECT
              *
            FROM
              shortest_path(
                'SELECT
                  gid AS id,
                  source::int4,
                  target::int4,
                  length::double precision AS cost
                FROM
                  ways
                WHERE
                    x1 > ".($minLon - $delta)." AND x1 < ".($maxLon + $delta)."
                    AND
                    x2 > ".($minLon - $delta)." AND x2 < ".($maxLon + $delta)."
                    AND
                    y1 > ".($minLat - $delta)." AND y1 < ".($maxLat + $delta)."
                    AND
                    y2 > ".($minLat - $delta)." AND y2 < ".($maxLat + $delta)."
                ',
                ?,
                ?,
                false,
                false
            ), array(
              $cityFrom['edge']['source'],
              $cityTo['edge']['target'],
      ));
      

      But it seems still not enough to find path between e.g. Moscow and Madrid in sufficient time, it takes now about minute. "SELECT .. FROM ways" still selects 2.4m of rows and takes all RAM that way.

      Maybe it is more related to PostgreSQL optimization than PgRouting?, but are there ways to improve speed?

      • Message #1742

        Well, it usually only depends on how much data you load. You should make sure the following points

        • Do you have indices?
        • Do you select only the data you need (take a bounding box for example, that contains all relevant data)
        • Check if you have very high ID's. It's better to renumber ID's in that case.
    • Message #1684

      Thank you. What do you mean by clever strategy load data? Site  http://maps.map.cloudmade.com search path takes a few seconds. How is this done?

      • Message #1685

        You should ask this question to Cloudmade, why they are so fast ;-)

        pgRouting is a library for a PostGIS database, so you don't load all your network into RAM in some pre-calculated compressed format. That's why it won't be possible to achieve the same performance as with those specialized routing services running in memory. On the other hand those are not able to provide the flexibility of pgRouting.

        Clever strategy would be for example that you make layers by road classes and take only layers with more important roads for long distance routing, and you only load the whole road network around start and end point.

        • Message #1692

          I downloaded the file russian_federation.osm.highway.bz2 (80.5M). With utility osmosis filtered the following types of roads: motorvay - tertiary.

          ./osmosis --read-xml file="$1" --way-key-value keyValueList="highway.motorway,highway.motorway_link,highway.trunk,highway.trunk_link,highway.primary,highway.primary_link,highway.secondary,highway.secondary_link,highway.tertiary " --write-xml file="filter1.osm"

          To generate the database used osm2pgroting. In the generated database, the number of entries in the table 'ways' decreased by 6 times the number of entries in the table 'nodes' are not changed. How can I reduce the number of 'nodes'?

          • Message #1693

            After using osm2pgrouting your table should look similar to this one

            pgrouting-workshop=# \d
                            Liste der Relationen
             Schema |        Name         |   Typ   | Eigentümer
            --------+---------------------+---------+------------
             public | geography_columns   | Sicht   | postgres
             public | geometry_columns    | Tabelle | postgres
             public | spatial_ref_sys     | Tabelle | postgres
             public | vertices_tmp        | Tabelle | postgres
             public | vertices_tmp_id_seq | Sequenz | postgres
             public | ways                | Tabelle | postgres
            (6 Zeilen)
            

            The table vertices_tmp is what you mean with "nodes table"? It's just used to populate the source/target columns in "ways" table, so you actually don't need it anymore later.

            Btw., you can specify in the osm2pgrouting configuration file, which ways you want to import. I haven't used osmosis for that, so can't tell much about.

            • Message #1749

              I want to join PostLBS programming and development. Because fisrt time join in the open source so many things not understood, I hope to receive help from you. First please, you help me explain the setup manual for window, I do not understand these instructions so I should not be done: http://pgrouting.postlbs.org/wiki/1.x/WindowsInstallationManual From section: Manual install CMAKE I do not understand the instructions as: #. / Configure - prefix = E: / Build/msys/1.0/local # Make # Make install is doing? Also I do not understand the lower part, with section Boost # Bjam-MinGW Stools = "-static sBUILD = release <runtime-link> <threading> multi <native-wchar_t> on" - prefix = / install e/Build/msys/1.0/local # Mv / usr/local/include/boost-1_33_1/boost / usr / local / include / boost # Rmdir / usr/local/include/boost-1_33_1 these sections aother too, hope to receive your help. my english is very bad, you try to understand and help me. thanks.