Выполнение геохеша в запросе диапазона памяти - PullRequest
Новая
       56

Выполнение геохеша в запросе диапазона памяти

0 голосов
/ 14 сентября 2018

Прежде всего я хотел бы сказать, что я не заинтересован в использовании Redis или любой другой пространственной БД. Я пытаюсь сделать очень упрощенный запрос диапазона геохэш-памяти в памяти, и я использую следующее программное обеспечение для вычисления пакета geohash- geohash-int C , и у меня есть оболочка Cython для вызова этих API в Python 3.6. Я использую SortedList для хранения геохешей, и моя цель - сделать простой запрос диапазона геохешей в памяти. 

#GeoHash is a Cython wrapper of external C geohash library (link provided)
from geo import GeoHash
from sortedcontainers import SortedList
import numpy as np

import time
minLat = 27.401436
maxLat = 62.54858
minLo = -180.0
maxLo = 179.95000000000002
latGrid = np.arange(minLat,maxLat,0.05)
lonGrid = np.arange(minLo,maxLo,0.05)
geoHash = GeoHash()

print(latGrid.shape,lonGrid.shape)
gridLon,gridLat = np.meshgrid(lonGrid,latGrid)
grid_points = np.c_[gridLon.ravel(),gridLat.ravel()]

sl = SortedList()
geohash1 = {}
t0 = time.time()
for grid_point in grid_points:
   lon = grid_point[0]
   lat = grid_point[1]
   geohash = geoHash.encode(lon,lat,26)
   bitsOriginal = geohash["bits"]
   sl.add(bitsOriginal)
   neighbors = geoHash.get_neighbors(geohash)
   for k,v in neighbors.items():
        bits1 = v["bits"]
        sl.add(bits1)
t1 = time.time()
print(t1-t0)
lonTest = 172.76843
latTest = 61.560745
geohashTest = geoHash.encode(lonTest,latTest,26)
bitsTest =    geohashTest["bits"]

Что я хочу сделать, это следующее 

it = sl.irange(bitsTest-window,bitsTest+window)

Мой вопрос: как мне вычислить окно? Я хочу, чтобы окно находилось в пределах 0,1 градуса или любого другого окна, которое я укажу. Я понятия не имею, как рассчитать окно. Весь пакет геохеш очень быстрый, и меня интересуют только приблизительные совпадения для моего запроса. Я считаю, что моя контрольная точка должна находиться в пределах «диапазона» входного набора данных, для которого я рассчитал геохеш, но я не знаю, как получить диапазон геохешей для моей точки запроса. Может кто-нибудь помочь?

UPDATE Предложенный ответ хорош, но имеет сложность O (N). Если существует сложность порядка O (log N), которая была бы приемлемой.

Ответы [ 2 ]

0 голосов
/ 15 сентября 2018

Геохеши спроектированы таким образом, чтобы два местоположения, расположенные рядом друг с другом, имели одинаковый префикс / значение.Википедия описывает алгоритм с примером.Насколько я понимаю, широта и долгота преобразуются в двоичные значения, а биты чередуются друг с другом.Например: 

In [33]: def geohash(lat, lng):
    ...:     "Approximate geohash algorithm."
    ...:     # Step 1: Convert to fixed-point.
    ...:     # I'm going to support six decimal places.
    ...:     lat = int(lat * 1e6)
    ...:     lng = int(lng * 1e6)
    ...:     # Step 2: Convert integers to 32-bit binary.
    ...:     lat = format(lat, '032b')
    ...:     lng = format(lng, '032b')
    ...:     # Step 3: Interleave bits from lat and lng.
    ...:     bits = [bit for pair in zip(lat, lng) for bit in pair]
    ...:     # Step 4: Convert bits to 64-bit integer.
    ...:     return int(''.join(bits), 2)
    ...: 
    ...: 

In [34]: lat, lng = 37.7749, 122.4194  # San Francisco, CA

In [35]: geohash(lat, lng)
Out[35]: 8215849339476576

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

In [38]: sf = geohash(lat, lng)

In [39]: lower_bounds = geohash(lat-0.001, lng-0.001)

In [40]: upper_bounds = geohash(lat+0.001, lng+0.001)

In [41]: lower_bounds < sf < upper_bounds
Out[41]: True

Теперь с нижними и верхними границами вы можете использовать SortedList.irange , чтобы найти все точки рядом с даннымширота и долгота за время O (log (n)).

0 голосов
/ 14 сентября 2018

Похоже, это должно быть возможно. Вы ищете точность 0,1 градуса. Конечно, сколько это в метрах, зависит от того, где вы находитесь на планете, и говорим ли мы о долготе или широте. Но вы можете рассчитать это. Исходя из этого, вы можете выяснить, каким должен быть минимальный префикс вашего геша для его прямоугольной формы. Более длинные хэши с тем же префиксом содержатся в прямоугольнике, который описывает меньший префикс.

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

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

Возможно, вы захотите проверить мою библиотеку https://github.com/jillesvangurp/geogeometry. Он имеет алгоритмы и функции для всего вышеперечисленного. Вы можете создавать круги, ограничивающие прямоугольники или многоугольники и покрывать их геохэшами заданной максимальной длины. Вы можете вычислить, какое значение подходит для этой максимальной длины, с помощью другой функции.

Он основан на Java, но должен легко переноситься на python или что-то еще, что вы хотите, учитывая, как я его структурировал. В основном это просто циклы и простая математика с использованием двойников.

Я фактически использовал это для реализации простого геопространственного поискового движка шесть лет назад. Очень хорошо масштабируется, если у вас есть база данных или поисковая система, которая может обрабатывать десятки миллионов геохешей Для небольших наборов данных вы можете легко сделать это в памяти.

...