Google App Engine Geohashing

I am writing a web application using GWT and App Engine. My application will need to post and query items based on their latitude, longitude.

As a result of google's distributed database design you can't simple query a set of inequalities. Instead they suggest doing geohashing. The method is described on this page.

http://code.google.com/appengine/articles/geosearch.html

Essentially you pre compute a bounding box so that you can query items that have been tagged with that bounding box.

There is one part of the process that I don't understand. What does the "slice" at开发者_如何学运维tribute mean?

Thanks for your help!

For a complete java portage of Geomodel, please see http://code.google.com/p/javageomodel/.

There is a demo class to explain you how to use it.

Rather than implementing the geohash yourself, you might be interested in the GeoModel open source project that implements a geohash-like system on Google App Engine. Rather than understanding all the details, you can just import this library and make calls like proximity_fetch() and bounding_box_fetch().

This more recent article describes how it works and provides an example that uses it.

Instead of defining a bounding box with 4 coordinates (min and max latitude, min and max longitude), you can define it with the coordinates of the North-West corner of the box, and two parameters : resolution and slice. The resolution defines the scale of the box, it is implemented as the number of figures below the decimal-point. The slice is the width and height of the box, using the least significant figure as its unit.

The comments in geobox.py explain this in more details, with good examples :

To query for members of a bounding box, we start with some input coordinates like lat=37.78452 long=-122.39532 (both resolution 5). We then round these coordinates up and down to the nearest "slice" to generate a geobox. A "slice" is how finely to divide each level of resolution in the geobox. The minimum slice size is 1, the maximum does not have a limit, since larger slices will just spill over into lower resolutions (hopefully the examples will explain).

Some examples:

resolution=5, slice=2, and lat=37.78452 long=-122.39532: "37.78452|-122.39532|37.78450|-122.39530"

resolution=5, slice=10, and lat=37.78452 long=-122.39532: "37.78460|-122.39540|37.78450|-122.39530"

resolution=5, slice=25, and lat=37.78452 long=-122.39532: "37.78475|-122.39550|37.78450|-122.39525"

I'm working on a GWT/GAE project and had the same problem. My solution was to use a Geohash class that I modified slightly to be GWT-friendly. It's great for my needs of proximity searches.

If you've never seen Geohashes in action, check out Dave Troy's JS demo page.

An alternative to do geo spatial searches in App Engine is the Search Api. You won't need to worry about geohashing or implementation details, and you'll be able to search for elements close to geo point.

https://developers.google.com/appengine/docs/python/search/overview#Performing_Location-Based_Searches

I was working on a GAE project with geohashing and this python library did the trick for me: http://mappinghacks.com/code/geohash.py.txt

I was also in need of a Java version of GeoModel. I was working with Geohash before, which allowed me to fetch locations in a given bounding box. But there are considerable limitations to this when it comes to sorting: in order to get BigTable to accept a filter like geohash > '" + bottomLeft + "' && geohash < '" + topRight + "'", you have to order the list by geohash as well, which makes it impossible to sort it by other criteria (especially if you want to use pagination). At the same time, I just can't think of a solution to sort the results by distance (from a given user-position, i.e. the center of the bounding box), other than in Java-code. Again, this will not work if you need to have pagination.

Because of these problems I had to use a different approach, and GeoModel/Geoboxes seemed to be the way. So, I ported the Python-code to Java and it's just working fine! Here is the result:

public class Geobox {

    private static double roundSlicedown(double coord, double slice) {
        double remainder = coord % slice;
        if (remainder == Double.NaN) {
            return coord;
        }
        if (coord > 0) {
            return coord - remainder + slice;
        } else {
            return coord - remainder;
        }
    }

    private static double[] computeTuple(double lat, double lng,
            int resolution, double slice) {
        slice = slice * Math.pow(10, -resolution);
        double adjustedLat = roundSlicedown(lat, slice);
        double adjustedLng = roundSlicedown(lng, slice);
        return new double[] { adjustedLat, adjustedLng - slice,
                adjustedLat - slice, adjustedLng };
    }

    private static String formatTuple(double[] values, int resolution) {
        StringBuffer s = new StringBuffer();
        String format = String.format("%%.%df", resolution);
        for (int i = 0; i < values.length; i++) {
            s.append(String.format(format, values[i]).replace(',','.'));
            if (i < values.length - 1) {
                s.append("|");
            }
        }
        return s.toString();
    }

    public static String compute(double lat, double lng, int resolution,
            int slice) {
        return formatTuple(computeTuple(lat, lng, resolution, slice),
                resolution);
    }

    public static List<String> computeSet(double lat, double lng,
            int resolution, double slice) {
        double[] primaryBox = computeTuple(lat, lng, resolution, slice);
        slice = slice * Math.pow(10, -resolution);
        List<String> set = new ArrayList<String>();
        for (int i = -1; i < 2; i++) {
            double latDelta = slice * i;
            for (int j = -1; j < 2; j++) {
                double lngDelta = slice * j;
                double[] adjustedBox = new double[] { primaryBox[0] + latDelta,
                        primaryBox[1] + lngDelta, primaryBox[2] + latDelta,
                        primaryBox[3] + lngDelta };
                set.add(formatTuple(adjustedBox, resolution));
            }
        }
        return set;
    }
}

sorry for the late answer, but I didn't return to this page for some time. A GeoDao implementation using the Geobox approach could look like this:

public class GeoDaoImpl extends DaoImpl<T extends GeoModel> {

    // geobox configs are: resolution, slice, use set (1 = true)
    private final static int[][] GEOBOX_CONFIGS = 
        { { 4, 5, 1 },
          { 3, 2, 1 },
          { 3, 8, 0 },
          { 3, 16, 0 },
          { 2, 5, 0 } };

    public GeoDaoImpl(Class<T> persistentClass) {
        super(persistentClass);
    }

    public List<T> findInGeobox(double lat, double lng, int predefinedBox, String filter, String ordering, int offset, int limit) {
        return findInGeobox(lat, lng, GEOBOX_CONFIGS[predefinedBox][0], GEOBOX_CONFIGS[predefinedBox][1], filter, ordering, offset, limit);     
    }

    public List<T> findInGeobox(double lat, double lng, int resolution, int slice, String filter, String ordering, int offset, int limit) {
        String box = Geobox.compute(lat, lng, resolution, slice);
        if (filter == null) {
            filter = "";
        } else {
            filter += " && ";
        }
        filter += "geoboxes=='" + box + "'";        
        return super.find(persistentClass, filter, ordering, offset, limit);
    }

    public List<T> findNearest(final double lat, final double lng, String filter, String ordering, int offset, int limit) {
        LinkedHashMap<String, T> uniqueList = new LinkedHashMap<String, T>();
        int length = offset + limit;
        for (int i = 0; i < GEOBOX_CONFIGS.length; i++) {       
            List<T> subList = findInGeobox(lat, lng, i, filter, ordering, 0, limit);
            for (T model : subList) {
                uniqueList.put(model.getId(), model);
            }
            if (uniqueList.size() >= length) {
                break;
            }
        }

        List<T> list = new ArrayList<T>();
        int i = 0;
        for (String key : uniqueList.keySet()) {
            if (i >= offset && i <= length) {
                list.add(uniqueList.get(key));
            }
            i++;
        }

        Collections.sort(list, new Comparator<T>() {
            public int compare(T model1, T model2) {                
                double distance1 = Geoutils.distFrom(model1.getLatitude(), model1.getLongitude(), lat, lng);
                double distance2 = Geoutils.distFrom(model2.getLatitude(), model2.getLongitude(), lat, lng);
                return Double.compare(distance1, distance2);
            }
        });

        return list;
    }

    @Override
    public void save(T model) {
        preStore(model);
        super.save(model);
    }

    private void preStore(T model) {
        // geoboxes are needed to find the nearest entities and sort them by distance
        List<String> geoboxes = new ArrayList<String>();
        for (int[] geobox : GEOBOX_CONFIGS) {
             // use set
             if (geobox[2] == 1) {
                 geoboxes.addAll(Geobox.computeSet(model.getLatitude(), model.getLongitude(), geobox[0], geobox[1]));
             } else {
                 geoboxes.add(Geobox.compute(model.getLatitude(), model.getLongitude(), geobox[0], geobox[1]));
             }
        }
        model.setGeoboxes(geoboxes);
    }

}