sis-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Peter Karich (JIRA)" <j...@apache.org>
Subject [jira] [Issue Comment Edited] (SIS-45) Performance improvement of queryByPointRadius
Date Sat, 21 Apr 2012 22:30:33 GMT

    [ https://issues.apache.org/jira/browse/SIS-45?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13258954#comment-13258954
] 

Peter Karich edited comment on SIS-45 at 4/21/12 10:30 PM:
-----------------------------------------------------------

Regarding the time which is always the same ... this was my fault. I thought the capacity
means the capacity of the whole quadtree, but it is the cap. per leaf node. But beside this
simplemindedness the performance improvements should be done nevertheless. 

Without the optimization and new QuadTree(16, 100)

{code}
10km:  66ms (~  60k results on every request)
20km: 261ms (~ 300k)
40km: 866ms (~ 850k)
{code}
with the change of a 'normed radius':
{code}
10km:  26ms (~  60k)
20km:  95ms (~ 300k)
40km: 298ms (~ 850k)
{code}
=> a 300% speedup, also it looks like it scales better.

The code is here: https://github.com/karussell/GraphHopper/tree/master/perf-comparison

Now that I understand the code better I do not understand why there is a maximum depth - just
to avoid programming errors? But to avoid that some entries are silently skipped (!) one needs
to set this to Integer.MAX (or a high value). Shouldn't the statment "if(maxDepthExceeded..."
just be executed in an assert statemnt not running in production code or this depth completely
removed?
                
      was (Author: peathal):
    Regarding the time which is always the same ... this was my fault. I thought the capacity
means the capacity of the whole quadtree, but it is the cap. per leaf node. But beside this
simplemindedness the performance improvements should be done nevertheless. 

Without the optimization and new QuadTree(16, 100)

10km:  66ms ( 83k results)
20km: 261ms (313k results)
40km: 866ms (1mio results)

with the change of a 'normed radius':

10km:  26ms ( 83k results)
20km:  95ms (313k results)
40km: 298ms (1mio results)

=> a 300% speedup, also it looks like it scales better.

The code is here: https://github.com/karussell/GraphHopper/tree/master/perf-comparison

Now that I understand the code better I do not understand why there is a maximum depth - just
to avoid programming errors? But to avoid that some entries are silently skipped (!) one needs
to set this to Integer.MAX (or a high value). Shouldn't the statment "if(maxDepthExceeded..."
just be executed in an assert statemnt not running in production code or this depth completely
removed?
                  
> Performance improvement of queryByPointRadius
> ---------------------------------------------
>
>                 Key: SIS-45
>                 URL: https://issues.apache.org/jira/browse/SIS-45
>             Project: Spatial Information Systems
>          Issue Type: Improvement
>            Reporter: Peter Karich
>
> If I didn't make a mistake a search with the normal distance method took ~2.4s and with
this distance method it takes only about 0.7s:
> {code}
>   public static double getHaversineDistance(double fromLat, double fromLon, double toLat,
double toLon) {
>     double dLat = Math.toRadians(toLat - fromLat);
>         double dLon = Math.toRadians(toLon - fromLon);
>         double a = Math.sin(dLat / 2) * Math.sin(dLat / 2)
>                 + Math.cos(Math.toRadians(fromLat)) * Math.cos(Math.toRadians(toLat))
* Math.sin(dLon / 2) * Math.sin(dLon / 2);
>         return EARTH_RADIUS * 2 * Math.asin(Math.sqrt(a));
>   }
> {code}
> Also one should think about normalizing the distance before the search so that one does
not need the whole last line which should give further speed improvements.
> I'm still unsure why it takes roughly the same time in my example for 10km, 20km and
40kmm where at every step a lot more nodes are involved. Normally I would say the mode nodes
- the more comparisons it'll take and the slower it should get. But it doesn't. Probably I'm
measuring wrong?

--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira

        

Mime
View raw message