Google App Engine Geohashing

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

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

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

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

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

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


person freakTheMighty    schedule 13.01.2010    source источник
comment
Вам не кажется, что можно было бы более конкретно задать свой вопрос? Не могли бы вы попросить меня найти экземпляр фрагмента, о котором вы говорите, или мне нужно прочитать всю эту огромную страницу?   -  person Adam Crossland    schedule 14.01.2010
comment
Пример нарезки, о котором я говорю, сначала описывается в разделе «Ввод местоположения». Помимо разрешения, мы также указываем «фрагмент». Срез - насколько точно разделить каждый уровень разрешения в геобоксе.   -  person freakTheMighty    schedule 18.01.2010


Ответы (8)


Полный перенос Java-модели Geomodel см. На странице http://code.google.com/p/javageomodel/.

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

person Alexandre Gellibert    schedule 26.02.2010

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

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

person npdoty    schedule 15.01.2010
comment
Вы знаете версию Java? Я планирую использовать Java API App Engine. - person freakTheMighty; 18.01.2010
comment
Я не знаю ни одного. Но не стесняйтесь портировать его самостоятельно;) Держу пари, что люди из Google, которые поддерживают Python GeoModel, захотят немного помочь. - person npdoty; 19.01.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"

person Stéphane    schedule 14.01.2010
comment
Мне кажется, что и уменьшение разрешения, и использование большего среза увеличивают размер ограничивающей рамки. Как подойти к определению этих параметров? Каковы компромиссы для различных разрешений и размеров фрагментов? - person freakTheMighty; 18.01.2010

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

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

person Eric Landry    schedule 23.01.2010

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

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

person Felipe Hoffa    schedule 20.05.2013

Я работал над проектом GAE с геохешированием, и эта библиотека Python помогла мне: http://mappinghacks.com/code/geohash.py.txt

person pokstad    schedule 01.02.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;
    }
}
person Thomas Baldauf    schedule 01.02.2010
comment
Похоже, что доступен Java-порт Python GeoModel: code.google.com/p/javageomodel < / а> - person npdoty; 09.03.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);
    }

}
person Thomas Baldauf    schedule 24.02.2010