Я ищу, чтобы оптимизировать время гео-поисков.
Я ввожу координаты широты и точки, и я ищу по заранее вычисленному набору местоположений для n ближайших точек.
Мне все равно, сколько времени / пространства займет построение предварительно вычисленного индекса местоположений, но мне все равно, что запросы будут очень быстрыми.
Я думаю об использовании geohash в качестве ключа поиска, где я сначала проверю, получу ли я результаты для X-символов ключа, а затем продолжу обрезать символы от конца ключа до тех пор, пока не начну видеть результаты.
Насколько мне известно (пока очень немного), о методах геоиндекса, этот подход должен дать самые быстрые результаты (с точки зрения времени запроса) по сравнению со всеми другими известными реализациями (такими как R Tree и co.)
Ответы:
Абсолютно вы можете. И это может быть довольно быстро. (Также могут быть распределены интенсивные биты вычислений)
Есть несколько способов, но один из способов, с которыми я работал, заключается в использовании упорядоченного списка геохешей на основе целых чисел и нахождении всех диапазонов геохешей ближайших соседей для определенного разрешения геохеша (разрешение приближается к вашим
distance
критериям), а затем запрашивая эти диапазоны геохэш, чтобы получить список ближайших точек. Для этого я использую redis и nodejs (т.е. javascript). Redis работает очень быстро и может очень быстро получать упорядоченные диапазоны, но он не может выполнять большую часть действий по обработке запросов индексирования, которые могут выполнять базы данных SQL.Метод описан здесь: https://github.com/yinqiwen/ardb/wiki/Spatial-Index
Но суть в этом (перефразируя ссылку):
Вы можете дополнительно оптимизировать (по скорости) это:
Вы можете еще больше повысить точность, используя функцию расстояния по окружности / тип haversine для возвращаемых результатов, если вы сильно заботитесь о точности.
Вот аналогичный метод, использующий обычные геохеши base32 и SQL-запрос вместо redis: https://github.com/davetroy/geohash-js
Я не хочу подключать свои собственные вещи, но я написал модуль для nodejs & redis, который делает это действительно простым в реализации. Посмотрите код, если хотите: https://github.com/arjunmehta/node-georedis
источник
Вопрос может быть прочитан несколькими способами. Я понимаю, что это означает, что у вас есть большое количество точек, и вы намереваетесь проверять их многократно с произвольными точками, заданными в виде координатных пар, и хотите получить n ближайших к зонду точек с заранее установленным n. (В принципе, если n будет меняться, вы можете настроить структуру данных для каждого возможного n и выбрать ее за O (1) раз для каждого зонда: это может занять очень длительное время установки и потребовать много оперативной памяти, но мы сказано игнорировать такие проблемы.)
Построить диаграмму порядка-Вороного всех точек. Это делит плоскость на связанные области, каждая из которых имеет одинаковые n соседей. Это сводит ситуацию к задаче точка-многоугольник, которая имеет много эффективных решений.
Используя векторную структуру данных для диаграммы Вороного, поиск точки в многоугольнике займет время O (log (n)). Для практических целей вы можете сделать это O (1) с чрезвычайно малым неявным коэффициентом, просто создав растровую версию диаграммы. Значения ячеек в растре являются либо (i) указателем на список из n ближайших точек, либо (ii) указанием на то, что эта ячейка расположена между двумя или более областями на диаграмме. Тест для произвольной точки в точке (x, y) становится:
Чтобы достичь производительности O (1), растровая сетка должна быть достаточно тонкой, чтобы относительно небольшое количество зондов попадало в ячейки, которые охватывают несколько областей Вороного. Это всегда может быть достигнуто с потенциально большими затратами на хранение для сетей.
источник
Я использую геохэш для именно этого. Причина в том, что мне нужно было осуществлять поиск по близости, используя информационную систему в стиле пирамиды ... где геохеши с точностью до 8-го уровня были "основой" и формировали новые итоги для гео-хешей с 7-й точностью ... и так далее, и так далее , Это были площадь, типы почвенного покрова и т. Д. Это был очень причудливый способ сделать что-то очень причудливое.
Таким образом, геохэш 8-го уровня будет содержать такую информацию, как:
Тип: трава акров: 1.23
и 7-е, 6-е .. и т. д. будет содержать информацию, как:
Типы травы: 123 акра: 6502
Это всегда было построено с самой низкой точностью. Это позволило мне очень быстро делать всевозможные забавные статистические данные. Я также смог назначить ссылку на геометрию для каждой ссылки на геохэш, используя GeoJSON.
Мне удалось написать несколько функций, чтобы найти самые большие геохеши, которые составляют мой текущий видовой экран, а затем использовать их, чтобы найти геохэш со второй по величине точностью в окне просмотра. Это можно легко распространить на запросы с индексированным диапазоном, где я запрашивал бы минимум 86ssaaaa и максимум 86sszzzz для любой точности, которую я хотел.
Я делаю это с помощью MongoDB.
источник
Обновление для 2018-х годов, и некоторые математические фонды или историческое происхождение Geohash:
Вдохновением для Геохаша было простое чередование двоичных цифр , возможно, оптимизация наивных алгоритмов, чередующих десятичные цифры, таких как C-квадраты .
бинарное чередование привело к стратегии индекса индекса Z-порядка, естественно, изобретатель Geohash не начал «искать лучшую фрактальную кривую» ... Но любопытно, что такая оптимизация дизайна, лучшая фрактальная кривая, возможна (!).
Использовать S2 Geometry Library
Геометрический подход S2 лучше, чем Geohash, потому что он использует сферическую топологию шара (куб), использует дополнительную проекцию (так что все ячейки имеют почти одинаковую форму и близкую область), и потому что индексирование с помощью кривой Гильберта лучше, чем Z- кривая порядка :
Теперь это бесплатная и эффективная библиотека, см. Https://s2geometry.io.
PS: есть также (хорошие) неофициальные упрощенные версии, такие как NodeJS
s2-geometry
, и множество «игровых площадок», надстроек и демонстраций, как s2.sidewalklabs.com .источник
Я бы порекомендовал использовать запрос GEORADIUS в Redis.
Передайте данные, защищенные наилучшим подходящим уровнем геохеша, с помощью вызова GEOADD.
Кроме того, посмотрите на это -> ProximityHash .
ProximityHash генерирует набор геохешей, которые покрывают круглую область, учитывая координаты центра и радиус. У него также есть дополнительная возможность использовать GeoRaptor, который создает наилучшую комбинацию геохешей на разных уровнях для представления круга, начиная с самого высокого уровня и итерируя до получения оптимальной смеси. Точность результатов остается такой же, как и у начального уровня геохеша, но размер данных значительно уменьшается, что повышает скорость и производительность.
источник