Google App Engine Geohashing - PullRequest
       27

Google App Engine Geohashing

12 голосов
/ 13 января 2010

Я пишу веб-приложение, используя GWT и App Engine. Мое приложение должно будет публиковать и запрашивать элементы на основе их широты и долготы.

В результате проектирования распределенной базы данных Google вы не можете просто запросить набор неравенств. Вместо этого они предлагают делать геохэшинг. Метод описан на этой странице.

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

По сути, вы предварительно вычисляете ограничивающий прямоугольник, чтобы можно было запрашивать элементы, помеченные этим ограничивающим прямоугольником.

Есть одна часть процесса, которую я не понимаю. Что означает атрибут «ломтик»?

Спасибо за вашу помощь!

Ответы [ 8 ]

7 голосов
/ 26 февраля 2010

Для полной версии Java Geomodel, пожалуйста, смотрите http://code.google.com/p/javageomodel/.

Существует демонстрационный класс, объясняющий, как его использовать.

6 голосов
/ 15 января 2010

Вместо того, чтобы реализовывать геохэш самостоятельно, вас может заинтересовать проект GeoModel с открытым исходным кодом, который реализует систему, похожую на геохэш, в Google App Engine. Вместо того, чтобы разбираться во всех деталях, вы можете просто импортировать эту библиотеку и делать вызовы, такие как proximity_fetch() и bounding_box_fetch().

В этой более свежей статье описывается, как она работает, и приводится пример, в которой она используется.

3 голосов
/ 23 января 2010

Я работаю над проектом GWT / GAE , и у меня возникла та же проблема. Мое решение состояло в том, чтобы использовать класс Geohash , который я немного изменил, чтобы сделать его более дружественным к GWT. Это отлично подходит для моих потребностей поиска близости.

Если вы никогда не видели Geohashes в действии, посмотрите демонстрационную страницу Дэйва Троя JS.

3 голосов
/ 14 января 2010

Вместо определения ограничивающего прямоугольника с 4 координатами (минимальная и максимальная широта, минимальная и максимальная долгота) вы можете определить его с помощью координат северо-западного угла поля и двух параметров: разрешения и среза. Разрешение определяет масштаб поля, оно реализовано в виде числа цифр ниже десятичной точки. Срез - это ширина и высота прямоугольника с использованием наименее значимой цифры в качестве единицы измерения.

Комментарии в geobox.py объясняют это более подробно, с хорошими примерами:

Для запроса членов ограничительной рамки мы начнем с некоторых входных координат как lat = 37,78452 long = -122,39532 (оба разрешения 5). Затем мы вокруг этих координаты вверх и вниз до ближайшего «среза» для создания геобокса. Ломтик" как тонко разделить каждый уровень разрешения в геобоксе. Минимум размер среза равен 1, максимальный не имеет ограничения, так как более крупные срезы будут просто перейдите на более низкие разрешения (надеюсь, примеры объяснят).

Некоторые примеры:

разрешение = 5, срез = 2 и широта = 37,78452, длина = -122,39532: "37,78452 | -122,39532 | 37,78450 | -122,39530"

разрешение = 5, срез = 10 и широта = 37,78452, длина = -122,39532: "37,78460 | -122,39540 | 37,78450 | -122,39530"

разрешение = 5, срез = 25 и широта = 37,78452, длина = -122,39532: "37,78475 | -122,39550 | 37,78450 | -122,39525"

1 голос
/ 20 мая 2013

Альтернативой для гео-пространственного поиска в App Engine является Search Api. Вам не нужно беспокоиться о геохашировании или деталях реализации, и вы сможете искать элементы, близкие к географической точке.

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

0 голосов
/ 25 февраля 2010

извините за поздний ответ, но я некоторое время не возвращался на эту страницу Реализация GeoDao с использованием подхода Geobox может выглядеть следующим образом:

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);
    }

}
0 голосов
/ 01 февраля 2010

Я работал над проектом GAE с геохэшингом, и эта библиотека Python сделала мне хитрость:

0 голосов
/ 01 февраля 2010

Мне также понадобилась Java-версия GeoModel. Раньше я работал с Geohash, что позволило мне выбирать места в заданной ограничительной рамке. Но это имеет значительные ограничения, когда дело доходит до сортировки: чтобы BigTable мог принять фильтр типа geohash > '" + bottomLeft + "' && geohash < '" + topRight + "'", нужно также упорядочить список по geohash, что делает невозможным сортировку по другим критериям (особенно если вы хотите использовать нумерацию страниц). В то же время я просто не могу придумать решение для сортировки результатов по расстоянию (от заданной пользовательской позиции, то есть от центра ограничительной рамки), за исключением Java-кода. Опять же, это не будет работать, если вам нужно иметь нумерацию страниц.

Из-за этих проблем мне пришлось использовать другой подход, и казалось, что GeoModel / Geoboxes - подход. Итак, я перенес Python-код на Java, и он просто отлично работает! Вот результат:

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;
    }
}
...