Używasz geohash do wyszukiwania w pobliżu?

Chcę zoptymalizować czas wyszukiwania geograficznego bliskości punktu.

Moje dane wejściowe to: długość, długość, punkt i szukam wstępnie obliczonego zestawu lokalizacji do n najbliższych punktów.

Nie dbam o to, ile czasu / miejsca zajmie zbudowanie wstępnie obliczonego indeksu lokalizacji, ale dbam o to, że zapytania będą super szybkie.

Zastanawiam się nad użyciem geohash jako klucza wyszukiwania, w którym najpierw sprawdzam, czy otrzymuję wyniki dla X znaków tego klucza, a następnie kontynuuję zmniejszanie znaków od końca klucza, aż zacznę widzieć wyniki.

Według mojego (bardzo rzadkiego na razie) zrozumienia technik indeksu geograficznego takie podejście powinno być w stanie zapewnić najszybsze wyniki (pod względem czasu zapytania) w porównaniu do wszystkich innych znanych implementacji (takich jak R Tree i wsp.)

Absolutnie możesz. I może być dość szybki. (Bity intensywnego obliczania można również dystrybuować)

Jest kilka sposobów, ale jednym ze sposobów, w jaki pracowałem, jest użycie uporządkowanej listy geohashów opartych na liczbach całkowitych i znalezienie wszystkich najbliższych sąsiednich zakresów geohashów dla określonej rozdzielczości geohash (rozdzielczość jest zbliżona do twoich distancekryteriów), a następnie sprawdzanie zakresów geohashów w celu uzyskania listy pobliskich punktów. Używam do tego redis i nodejs (tj. Javascript). Redis jest super szybki i może bardzo szybko wyszukiwać uporządkowane zakresy, ale nie może wykonywać wielu czynności związanych z manipulowaniem zapytaniami indeksującymi, jakie mogą wykonywać bazy danych SQL.

Metodę opisano tutaj: https://github.com/yinqiwen/ardb/wiki/Spatial-Index

Ale jego sedno to (parafrazując link):

1. Przechowujesz wszystkie swoje geohashed punkty w najlepszej, pożądanej rozdzielczości (zazwyczaj 64-bitowa liczba całkowita, jeśli jest dostępna, lub w przypadku javascript, 52 bity) w uporządkowanym zestawie (tj. Zset in redis). Większość bibliotek geohash ma obecnie wbudowane funkcje liczb całkowitych geohash i będziesz musiał ich używać zamiast bardziej powszechnych geohashów base32.
2. W oparciu o promień, który chcesz przeszukać, musisz znaleźć głębokość / rozdzielczość bitową, która będzie pasować do twojego obszaru wyszukiwania, a ta musi być mniejsza lub równa zapisanej głębokości bitowej geohash. Witryna, do której prowadzi łącze, ma tabelę, która koreluje głębokość bitów geohash z obszarem obwiedni w metrach.
3. Następnie ponownie odtworzysz swoją pierwotną współrzędną w niższej rozdzielczości.
4. Przy tej niższej rozdzielczości znajdź także 8 sąsiadujących obszarów (n, ne, e, se, s, sw, w, nw) geohash. Powodem, dla którego musisz wykonać metodę sąsiada, jest to, że dwie współrzędne blisko siebie mogą mieć zupełnie inne geohashy, więc musisz zrobić jakieś uśrednienie obszaru objętego wyszukiwaniem.
5. Po uzyskaniu wszystkich sąsiadów geohash przy tej niższej rozdzielczości dodaj do listy geohash współrzędnych z kroku 3.
6. Następnie musisz zbudować zakres wartości geohash, aby wyszukać w obrębie tych 9 obszarów. Wartości z kroku 5 są dolnym limitem zakresu, a jeśli dodasz 1 do każdego z nich, otrzymasz górny limit zakresu. Powinieneś więc mieć tablicę 9 zakresów, każdy z dolnym i górnym limitem geohash (łącznie 18 geohashów). Te geohashy są nadal w niższej rozdzielczości od kroku 2.
7. Następnie konwertujesz wszystkie 18 tych geohashów na dowolną głębokość / rozdzielczość bitów, w której zapisałeś wszystkie geohashy w swojej bazie danych. Zasadniczo robisz to poprzez przesunięcie bitów do żądanej głębokości bitów.
8. Teraz możesz wykonać zapytanie o zakres dla punktów w tych 9 zakresach, a otrzymasz wszystkie punkty w przybliżeniu w odległości od pierwotnego punktu. Nie będzie nakładania się, więc nie musisz robić żadnych skrzyżowań, tylko zapytania o czysty zakres, bardzo szybko. (tj. in redis: ZRANGEBYSCORE zsetname lowerLimit upperLimit, w 9 zakresach utworzonych w tym kroku)

Możesz dalej zoptymalizować (pod względem prędkości) to:

1. Biorąc te 9 zakresów od kroku 6 i znajdując, gdzie prowadzą do siebie. Zwykle można zmniejszyć 9 oddzielnych zakresów do około 4 lub 5, w zależności od położenia współrzędnej. Może to skrócić czas zapytania o połowę.
2. Po uzyskaniu ostatecznych zasięgów powinieneś zatrzymać je do ponownego użycia. Obliczenie tych zakresów może zająć większość czasu przetwarzania, więc jeśli pierwotna współrzędna niewiele się zmienia, ale musisz ponownie zadać to samo zapytanie o odległość, powinieneś zachować tę gotowość zamiast obliczać ją za każdym razem.
3. Jeśli używasz redis, spróbuj połączyć zapytania w MULTI / EXEC, aby potokować je w celu uzyskania nieco lepszej wydajności.
4. NAJLEPSZA część: możesz rozprowadzać kroki 2-7 na klientach zamiast wykonywać te obliczenia w jednym miejscu. To znacznie zmniejsza obciążenie procesora w sytuacjach, w których przychodziłyby miliony żądań.

Możesz jeszcze bardziej zwiększyć dokładność, używając funkcji odległości koła / typu haverine na zwracanych wynikach, jeśli zależy Ci na precyzji.

Oto podobna technika przy użyciu zwykłych geohashów base32 i zapytania SQL zamiast redis: https://github.com/davetroy/geohash-js

Nie zamierzam podłączać własnych rzeczy, ale napisałem moduł dla nodejs i redis, który sprawia, że ​​jest to naprawdę łatwe do wdrożenia. Spójrz na kod, jeśli chcesz: https://github.com/arjunmehta/node-georedis

Pytanie można odczytać na kilka sposobów. Rozumiem, że masz dużą liczbę punktów i zamierzasz sondować je wielokrotnie dowolnymi punktami, podanymi jako pary współrzędnych, i chcesz uzyskać n najbliższych punktów do sondy, z n ustalonymi wcześniej. (Zasadniczo, jeśli n będzie się różnić, możesz skonfigurować strukturę danych dla każdego możliwego n i wybrać ją w czasie O (1) z każdą sondą: może to zająć bardzo długi czas konfiguracji i wymagać dużej ilości pamięci RAM, ale my mówi się, aby ignorować takie obawy).

Zbuduj diagram porządku Voronoi dla wszystkich punktów. Dzieli to płaszczyznę na połączone obszary, z których każdy ma tych samych n sąsiadów. Zmniejsza to sytuację do problemu punkt-w-wielokącie, który ma wiele skutecznych rozwiązań.

Wykorzystując wektorową strukturę danych dla diagramu Voronoi, wyszukiwanie punkt-wielobok zajmie czas O (log (n)). Dla celów praktycznych możesz zrobić ten O (1) z wyjątkowo małym domyślnym współczynnikiem, po prostu tworząc wersję rastrową diagramu. Wartości komórek w rastrze to (i) wskaźnik do listy n najbliższych punktów lub (ii) wskazanie, że komórka rozciąga się na dwóch lub więcej obszarach na diagramie. Test na dowolny punkt w (x, y) staje się:

Fetch the cell value for (x,y).
If the value is a list of points, return it.
Else apply a vector point-in-polygon algorithm to (x,y).

Aby osiągnąć wydajność O (1), siatka rastrowa musi być wystarczająco drobna, aby względnie niewiele punktów sondy spadło w komórkach otaczających wiele regionów Voronoi. Zawsze można to osiągnąć przy potencjalnie dużym koszcie przechowywania sieci.

Właśnie do tego używam geohashów. Powodem, dla którego jestem, jest to, że musiałem przeprowadzić wyszukiwanie zbliżeniowe za pomocą systemu informacyjnego w stylu piramidy .. w którym geohashy z dokładnością 8 poziomu były „bazą” i utworzyły nowe sumy dla geohashów z 7 precyzji… i tak dalej i tak dalej . Te sumy to powierzchnia, rodzaje pokrycia gruntu itp. To był bardzo fantazyjny sposób na zrobienie bardzo fantazyjnych rzeczy.

Geohashy 8-go poziomu zawierałyby takie informacje, jak:

typ: akry traw: 1,23

i 7., 6. .. itd. zawierałyby informacje takie jak:

grass_types: 123 akrów: 6502

To zawsze było budowane z najniższej precyzji. Umożliwiło mi to bardzo szybkie tworzenie wszelkiego rodzaju statystyk dotyczących zabawy. Byłem także w stanie przypisać odniesienie geometrii do każdego odniesienia geohash za pomocą GeoJSON.

Byłem w stanie napisać kilka funkcji, aby znaleźć największe geohashy, które składają się na moją bieżącą rzutnię, a następnie użyć tych, aby znaleźć geohashy o drugiej największej precyzji w rzutni. Można to łatwo rozszerzyć na zapytania o indeksowane zakresy, w których zapytałbym o minimum „86ssaaaa” i maksymalnie „86sszzzz” dla dowolnej precyzji, jakiej chciałem.

Robię to za pomocą MongoDB.

Aktualizacja na 2018 rok i niektóre matematyczne fundacje lub historyczne pochodzenie Geohash:

• inspiracji do Geohash był prosty interlave cyfr binarnych , może optymalizacja naiwnych algorytmów, które przeplatają się ze sobą cyfry dziesiętne, jak OF C kwadratów .

• przeplatanie binarne skutkowało oczywiście strategią indeksu krzywej rzędu Z , wynalazca Geohash nie zaczął „szukać najlepszej krzywej fraktalnej” ... Ale, co ciekawe, ta optymalizacja projektu, lepsza krzywa fraktalna, jest możliwa (!).

Użyj biblioteki geometrii S2

Geometria S2 jest lepsza niż Geohash, ponieważ wykorzystuje kulistą topologię globu (sześcian), stosuje opcjonalne rzutowanie (aby wszystkie komórki miały prawie taki sam kształt i bliski obszar), a ponieważ indeksowanie za pomocą krzywej Hilberta jest lepsze niż Z- krzywa kolejności :

... możemy zrobić lepiej ... Nieciągłość, gdy przechodzimy od prawego górnego do lewego dolnego kwadratu powoduje, że musimy podzielić niektóre zakresy, które w innym przypadku moglibyśmy przydzielić. (...) możemy całkowicie wyeliminować wszelkie nieciągłości (...)
blog.notdot.net/2009 w sprawie indeksowania przestrzennego za pomocą Quadtrees i Hilbert Curves

Teraz jest to darmowa i wydajna biblioteka, patrz https://s2geometry.io

PS: istnieją również (dobre) nieoficjalne wersje uproszczone, takie jak NodeJSs2-geometry , oraz wiele „placów zabaw”, dodatków i wersji demo, jak s2.sidewalklabs.com .

Polecam użycie zapytania GEORADIUS w redis.

Przekaż dane podzielone na segmenty według najlepiej dopasowanego poziomu geohash za pomocą wywołania GEOADD.

Zobacz także -> ProximityHash .

ProximityHash generuje zestaw geohashów pokrywających obszar kołowy, biorąc pod uwagę współrzędne środka i promień. Ma również dodatkową opcję użycia GeoRaptora, który tworzy najlepszą kombinację geohashów na różnych poziomach do reprezentowania koła, zaczynając od najwyższego poziomu i iteracji aż do warzenia optymalnej mieszanki. Dokładność wyniku pozostaje taka sama jak początkowego poziomu geohash, ale rozmiar danych znacznie się zmniejsza, poprawiając w ten sposób szybkość i wydajność.