sis-commits mailing list archives

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

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

Peter Karich edited comment on SIS-45 at 4/19/12 8:25 PM:
----------------------------------------------------------

Normalizing the distance leeds to some more improvements (0.5s):

{code}
   double normedRadius =  DistanceUtils.getNormalizedDist(radiusKM);
   ...  queryByPointRadius(point, normedRadius, ..
{code}

{code}
   if (DistanceUtils.getNormedHaversineDistance(data[i].getLatLon().getLat(), data[i]
              .getLatLon().getLon(), point.getLat(), point.getLon()) <= normedRadius) {
            matches.add(data[i]);
          }
{code}

with:

{code}
  public static double getNormedHaversineDistance(double fromLat, double fromLon, double toLat,
double toLon) {
    double dLat = Math.toRadians(toLat - fromLat);
        double dLon = Math.toRadians(toLon - fromLon);
        return 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);
  }

  public static double getNormalizedDist(double radiusKM) {
    double tmp = Math.sin(radiusKM / 2 / EARTH_RADIUS);
    return tmp * tmp;
  }
{code}

but I still feel bad (programming in the dark without unit tests ...)
                
      was (Author: peathal):
    Normalizing the distance leeds to some more (20%) improvements:

{code}
   double normedRadius =  DistanceUtils.getNormalizedDist(radiusKM);
   ...  queryByPointRadius(point, normedRadius, ..
{code}

{code}
   if (DistanceUtils.getNormedHaversineDistance(data[i].getLatLon().getLat(), data[i]
              .getLatLon().getLon(), point.getLat(), point.getLon()) <= normedRadius) {
            matches.add(data[i]);
          }
{code}

with:

{code}
  public static double getNormedHaversineDistance(double fromLat, double fromLon, double toLat,
double toLon) {
    double dLat = Math.toRadians(toLat - fromLat);
        double dLon = Math.toRadians(toLon - fromLon);
        return 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);
  }

  public static double getNormalizedDist(double radiusKM) {
    double tmp = Math.sin(radiusKM / 2 / EARTH_RADIUS);
    return tmp * tmp;
  }
{code}

but I still feel bad (programming in the dark without unit tests ...)
                  
> 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