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.)
Odpowiedzi:
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
distance
kryterió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):
Możesz dalej zoptymalizować (pod względem prędkości) to:
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
źródło
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ę:
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.
źródło
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.
źródło
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 :
Teraz jest to darmowa i wydajna biblioteka, patrz https://s2geometry.io
PS: istnieją również (dobre) nieoficjalne wersje uproszczone, takie jak NodeJS
s2-geometry
, oraz wiele „placów zabaw”, dodatków i wersji demo, jak s2.sidewalklabs.com .źródło
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ść.
źródło