Distances between houses, Google Directions API query limit is too low, need better algorithm

I need to rent two houses. I want them to be as close as possible. There are about 300 houses available for rent. I wish to use the Google Maps Directions API to calculate the walking distance between any two available houses so then I can sort the list and choose two that are close.

Everything works great, except that Google sets a theoretical limit of 2,500 queries per day (and in practice the limit is much lower, at only 250 per day). I have 300²/2 - 300 = 44,700 queries to make so obviously this limit is not enough for me.

This would be a one开发者_开发百科 time thing, any hints on how can I accomplish what I need with the Google Maps API? Can I somehow run the program distributed so the limit will affect only one instance? Would Google App Engine help?

I also welcome advice for improving the algorithm. If two houses are far apart, and another house is close to one of them it means it would not have to check the third house with the remaining house as they are probably far away. I also care more about the qualitative nature of the algorithm, not the exact distances, so maybe there is a simple approximation I can make that will result in fewer queries.

Thanks,

The geographic distance between any two houses, as the crow flies, will be a strict lower bound on the walking distance. So I'd start with 300 queries, to get the long/lat for each house, plug them into the Haversine formula (for example) to get the distances between the 45,000 unordered pairs, and sort them to get the closest pairs by geographic distance. Then with some likely candidates in hand, you can start checking the walking distances with another set of calls to the Google API.

Consider, that you are pizza deliverer and you want to calculate your effective range (where you can go within 30 minutes). And you want to make a colored bar 3d graph of N to E section of that time data, something like (with bogus data):

And you want to include like 100k of houses ... Well at least I heard, that program like this, was made before limits where introduced in Google map. Limits just bite hard in this case.

If you have geo location from all the houses, then you can find a prediction from how far are the points on earth, when you fly like a bird. Sort them based on that, and find results for best predictions.

Edit: Added Java code example, that could be useful when creating predictions:

/**
 * Thaddeus Vincenty's inverse method formulae implementation for
 * geographical distance between two given points on earth.
 * @param L1
 *        geographical latitude of standpoint in decimal degrees
 * @param G1
 *        geographical longitude of standpoint in decimal degrees
 * @param L2
 *        geographical latitude of destination in decimal degrees
 * @param G2
 *        geographical longitude of destination in decimal degrees
 * @return Geographical distance in kilometeres
 */
public static double getDistance(final double L1, final double G1,
        final double L2, final double G2) {
    double delta, p0, p1, p2, p3;
    // The average radius for a spherical approximation of Earth
    double rEarth = 6371.01d;

    delta = G1 - G2;
    p0 = Math.cos(L2) * Math.cos(delta);
    p1 = Math.cos(L2) * Math.sin(delta);
    p2 = Math.cos(L1) * Math.sin(L2) - Math.sin(L1) * p0;
    p3 = Math.sin(L1) * Math.sin(L2) + Math.cos(L1) * p0;

    return rEarth * Math.atan2(Math.sqrt(p1 * p1 + p2 * p2), p3);
}

/**
 * Rounds double to nr number of decimal places
 * @param d
 *        floating-point number
 * @param nr
 *        decimal places to keep
 * @return rounded number with nr decimal places
 */
public static double round(double d, int nr) {
    return new java.math.BigDecimal(Double.toString(d)).setScale(nr,
        java.math.BigDecimal.ROUND_HALF_UP).doubleValue();
}

public static void main(String[] args) {
    double L1 = Math.toRadians(Double.parseDouble(args[0]));
    double G1 = Math.toRadians(Double.parseDouble(args[1]));
    double L2 = Math.toRadians(Double.parseDouble(args[2]));
    double G2 = Math.toRadians(Double.parseDouble(args[3]));

    System.out.println(round(getDistance(L1, G1, L2, G2), 2));
}

i would use this formula :

distance = Math.acos(Math.sin(lat1)*Math.sin(lat2) + 
           Math.cos(lat1)*Math.cos(lat2) *
           Math.cos(lon2-lon1)) * 6371;

to rank all 45,000 houses by distance as the crow flies. I would then take the top 250 results ranked by shortest distance and run them through google to get the accurate walking distance and re-rank.

I don't know if this is working with the directions method but you want to interleave (nesting) the directions query into a single query. A google chunk can hold up to 24 directions per chunk. Thus you can increase your query to a maximum of 250 * 24 (6000 directions) per day. Maybe you want to change your IP adress after 6000 queries? Maybe Google let you then query more then 6000 directions per day? I got the interleaving idea from geweb tsp solver where he interleaves 24 cities from a query matrix into 1 chunk saving up to 22 single queries and thus reducing bandwidth and Google's API limitation.