Czy jest jakiś sposób, aby użyć magazynu klucz-wartość dla danych geoprzestrzennych?

26

W przeszłości korzystałem z wielu relacyjnych baz danych, ale czytałem także o wszystkich bazach danych NoSQL, a sklepy Key-Value wyglądają interesująco.

Kiedy przechowuję obiekt geometryczny, używam głównie pięciu indeksowanych kolumn ID, MIN_X, MAX_X, MIN_Y i MAX_Y (gdzie X i Y są w rzutach mapy). Nie potrzebuję indeksu dla moich innych danych.

Potrzebuję wartości X i Y, aby wyszukać obiekty w określonym miejscu (prostokąt mapy) i potrzebuję wartości ID, jeśli chcę zaktualizować określony obiekt.

Czy jest jakiś sposób, aby użyć do tego sklepu Key-Value?

database key-value-store nosql Jonas
źródło

Odpowiedzi:

18

Używamy Google AppEngine do uruchamiania zapytań przestrzennych / atrybutów, a głównym problemem (od pierwszego dnia) jest sposób indeksowania dużych zestawów linii / wielokątów o dowolnym rozmiarze. Dane punktowe nie są zbyt trudne (patrz geohash, geomodel itp.), Ale zestawy losowo zgrupowanych małych / dużych wielokątów zawsze stanowiły problem (aw niektórych przypadkach nadal występuje)

Wypróbowałem kilka różnych wersji indeksowania przestrzennego na GAE, ale większość z nich to tylko dwa warianty poniżej. Żadne z nich nie było tak szybkie jak bazy danych SQL i wszystkie mają zalety / wady. kompromisy wydają się rozsądne w przypadku większości aplikacji do mapowania przez Internet. Ponadto dwa poniższe muszą być połączone z buforowaniem geometrii w pamięci (poprzez JTS itp.), Aby usunąć wszelkie funkcje, które nie pasują do ostatecznych parametrów wyszukiwania. i wreszcie, opierają się na specyficznych funkcjach GAE, ale jestem pewien, że można by go zastosować do innych architektur (lub użyć TyphoonAE do uruchomienia na klastrze linux, ec2 itp.)

Siatki - spakuj wszystkie funkcje dla określonego obszaru do znanego indeksu siatki. Umieść mały indeks przestrzenny na siatce, aby szybko nawigować po zestawie funkcji, które on zawiera. W przypadku większości zapytań wystarczy wyciągnąć garść siatek, co jest szybkie, ponieważ znasz dokładną konwencję nazewnictwa siatki i jej związek z jednostkami K / V (pobiera, a nie zapytania)

Plusy - dość szybkie, łatwe do wdrożenia, nie zajmują miejsca w pamięci.

Wady - konieczne jest wstępne przetwarzanie, użytkownik musi zdecydować o wielkości siatki, duże geomy są współdzielone na kilku sieciach, klastrowanie może powodować przeciążenie sieci, problemy z serializacją / deserializacją mogą stanowić problem (nawet po skompresowaniu przez bufory protokołu)

QuadKeys - To jest bieżąca implementacja. w zasadzie jest taki sam jak siatki, z tym że nie ma ustalonego poziomu siatki. w miarę dodawania funkcji są one indeksowane według siatki quadkey, która całkowicie zawiera ich granice (lub w niektórych przypadkach, podzielona na dwie części, gdy pojedynczy quadkey nie może być użyty, pomyśl linię danych). Po znalezieniu qk jest on następnie dzielony na maksymalną liczbę mniejszych qk, które zapewniają dokładniejsze odwzorowanie ziarna cechy. wskaźnik / bbox do tej funkcji jest następnie pakowany do lekkiego gridindex (grupa funkcji), do którego można uzyskać zapytanie (oryginalny projekt bezpośrednio sprawdzał funkcje, ale okazało się to zbyt wolne / intensywnie obciążające procesor w przypadkach, gdy zestaw wyników był duży)

Polyline Quadkeys http://www.arc2earth.com/images/help/GAE_QKS_1.png Polygon Quadkeys http://www.arc2earth.com/images/help/GAE_QKS_2.png

Konwencja nazewnictwa quadkey zastosowana powyżej jest dobrze znana i, co ważniejsze, dąży do zachowania lokalizacji (opisana bardziej tutaj )

Wielokąt powyżej wygląda mniej więcej tak: 0320101013123 03201010131212 03201010131213 0320101013132 0320101013133 03201010131302 03201010131303 032010101313002 032010101313003 032010101313012 032010101311313132010101313131313 03201010131313131320101013131313132010101313131313 03101013133 1313 0310101313131313 0310101313131313 0310101313131313 0310101313131313 03101013133131310101313103

jeśli granice zapytania są wystarczająco małe, możesz bezpośrednio pobrać za pomocą qk. jest to optymalne, ponieważ jest to tylko pojedyncze, wsadowe wywołanie rpc do bazy danych GAE. jeśli granice są na tyle duże, że zawierały zbyt wiele możliwych qk (> 1000), możesz alternatywnie wykonać zapytanie za pomocą filtru (np .: qk> = 0320101013 i qk <= 0320101013 + \ ufffd). Konwencja nazewnictwa quadkey oraz sposób indeksowania ciągów GAE pozwala powyższemu zapytaniu pobrać tylko istniejące siatki, które spadają poniżej tej wartości qk.

istnieją inne zastrzeżenia i problemy z perfem, ale ogólnie jego zdolność do zapytania o quadkeys sprawia, że ​​jest to wykonalne

przykłady - zapytanie o hrabstwa USA: geojson

Plusy - dość szybko, bez konfiguracji rozmiaru siatki, bez pamięci, bez przepełnienia sieci

Wady - konieczne jest wstępne przetwarzanie, możliwe przekroczenie niektórych scenariuszy, brak danych biegunowych

Krzywe wypełniania przestrzeni - spójrz na dyskusję Alfreda na temat zapytań NextGen w Google I / O w tym roku. Włączenie ogólnych krzywych wypełniania przestrzeni / czasu wraz z nowymi operatorami MultiQuery (równolegle) pozwoli na naprawdę fajne zapytania przestrzenne. Czy pobije tradycyjną wydajność SQL? Trudno powiedzieć, ale powinno się dobrze skalować. Szybko zbliżamy się do przyszłości, w której zawsze dostępne urządzenia mobilne wszystkich kształtów i rozmiarów znacznie zwiększą ruch w Twojej witrynie / usłudze.

wreszcie zgodziłbym się również, że powinieneś bardzo uważnie przyjrzeć się swojej domenie problemowej przed wybraniem NoSQL zamiast SQL. W naszym przypadku bardzo podobał mi się model wyceny GAE, więc naprawdę nie było wyboru, ale jeśli nie musisz skalować, zaoszczędź trochę czasu i po prostu użyj standardowej bazy danych sql

b Powódź
źródło
Wspominasz GAE, ale jakiej bazy danych używasz? Jest ich kilka: cloud.google.com/products/storage
Don McCurdy
11

Słyszałem o GeoCouch, który jest implementacją CouchDB dla danych lokalizacyjnych. Myślę też, że MongoDB ma możliwości indeksowania geoprzestrzennego.

JoshFinnie
źródło
Tak, oboje tak, a SimpleGeo buduje przestrzenne rozszerzenie dla Cassandry. Nic nie słyszałem w Voldemort ani MemCache
TheSteve0
Och, uwielbiam to, co robi SimpleGeo. Jestem zazdrosny i chciałbym dla nich pracować!
JoshFinnie
8

Jest to głównie pytanie o algorytmy. Przepełnienie stosu może być również dobrym miejscem do tego.

W każdym razie odpowiedź na twoje bezpośrednie pytanie brzmi „tak, możesz użyć sklepu kvp do reprezentowania danych przestrzennych”. Lepszym pytaniem może być jednak „POWINIENEM używać magazynu kvp do reprezentowania danych przestrzennych?”

Odpowiedź na to pytanie (jak wiele innych) brzmi „to zależy”. Zależy to od skali, obciążenia (transakcyjnego) pracy, charakteru danych i infrastruktury obliczeniowej, którą masz do dyspozycji.

Magazyn kvp będzie miał niski narzut, co może pomóc w zwiększeniu przepustowości w przypadku dużych ilości równoległości wstawiania i aktualizacji. Nie będzie to jednak bardzo szybkie wyszukiwanie przestrzenne (znajdź wszystkie obiekty w prostokącie). W tym celu potrzebujesz indeksu przestrzennego, takiego jak R-Tree.

Jeśli jednak masz naprawdę duży wolumin danych i ogromny klaster komputerów, to użycie indeksu kvp może zapewnić pewne korzyści w zakresie wydajności. Jedynym sposobem, aby naprawdę się upewnić, jest wykonanie pomiarów perfów przy użyciu rzeczywistych danych i dostęp do szablonów, których można się spodziewać.

Aktualizacja :

Oto trochę więcej informacji. Możesz użyć sklepu KVP do wyszukiwania przestrzennego. Problem polega na tym, że jest powolny. Aby zobaczyć dlaczego, rozważ coś takiego:

  ***********
  ***********
  ***********
  ***********
  ****###****
  ****###****
  ****###****
  ***********
  ***********
  ***********
  ***********

Gdzie * i # reprezentują obiekty ułożone w siatce 11 x 11, których początek znajduje się w lewym górnym rogu. Wyobraź sobie wyszukiwanie obiektów w prostokącie (4,4) - (7,7). To powinno znaleźć wszystkie „#”. Zakładając, że używasz drzewa b + do reprezentowania swoich indeksów w sklepie KVP, możesz znaleźć wyniki za pomocą indeksu „X” lub indeksu „Y”. W tym przypadku nie ma znaczenia który. Dla celów dyskusji użyję indeksu x. Zrobiłbyś przeglądanie dziennika (n) w indeksie X, aby znaleźć pierwszy węzeł o wartości X „4”, a następnie iterować przez węzły liścia drzewa b +, aż znajdziesz węzeł o wartości większej niż 7. W miarę jak iteruj przez indeks x, a następnie odrzucisz wszystko, co jest poza pożądanym zakresem y.

To jest powolne. Wyobraź to sobie na dużej siatce o tej samej gęstości, powiedzmy 100 K * 100 K. W takim przypadku musiałbyś zeskanować wpisy indeksu „300 000”, aby znaleźć tylko 9 rekordów. Jeśli jednak użyjesz odpowiednio zbalansowanego drzewa R, wówczas wyszukiwanie indeksu prawdopodobnie wymagałoby jedynie zeskanowania około 90 rekordów. To ogromna różnica.

Problem polega jednak na tym, że utrzymanie zbalansowanego drzewa R jest kosztowne. Dlatego odpowiedź brzmi „to zależy” i dlaczego pytanie „powinienem to zrobić” jest o wiele ważniejsze niż „jak to zrobić”.

Jeśli często wstawiasz i usuwasz rekordy i przeszukujesz głównie „identyfikator obiektu”, a często nie wyszukujesz „przestrzennie”, to użycie twojego indeksu KVP da ci lepszą wydajność do tego, do czego tak naprawdę chcesz używać systemu . Jeśli jednak wstawiasz lub usuwasz rzadko, ale często przeszukujesz przestrzennie, to chcesz użyć R-drzewa.

Scott Wiśniewski
źródło
Nie zaakceptowałbym odpowiedzi typu „tak, możesz”. bo chcę wiedzieć JAK . A „POWINIENEM…” nie jest lepszym pytaniem, ponieważ, jak powiedziałeś „zależy”.
Jonas
1
Muszę się z tobą nie zgadzać. Jeśli chcesz zbudować użyteczny system lub pozostawić przydatne informacje w Internecie dla innych osób budujących podobne systemy, wtedy „powinienem” jest o wiele ważniejsze niż „jak”. Jednak w celu bycia pomocnym, edytowałem moją odpowiedź, aby podać informacje na temat tego, jak to zrobić.
Scott Wiśniewski
@Jonas Uważam, że odpowiedzi na „porady” wynikały ze sposobu, w jaki zadałeś pytanie: „ale przeczytałem również o wszystkich bazach danych NoSQL, a sklepy z kluczowymi wartościami wyglądają interesująco”. Ma to wszystkie cechy rozwiązania szukającego problemu.
JasonBirch
NoSQL nie rozwiązuje problemu, ale jest to problem, którego praktycznie nikt nie ma, ponieważ nie działa on na tak dużą skalę. Niestety zawsze miło jest myśleć, że nasze własne systemy są większe w wielkim schemacie rzeczy niż są w rzeczywistości. :)
JamesRyan
1

W większości przypadków więcej relacyjnych narzędzi do przechowywania danych uzyskasz niż z klucza / wartości lub klucza / wartości / typu. Wydajne zapytania i raporty dotyczące tego rodzaju schematów danych są bardzo skomplikowane.

Radzę dokładnie przeanalizować, czy twoja waga rzeczywiście wymaga NoSQL, zanim zastanowisz się, jak go używać.

JasonBirch
źródło
1
Oto przykład problemu, który możesz mieć (i jego rozwiązanie), jeśli chcesz obliczyć, czy punkt znajduje się wewnątrz czy na zewnątrz geometrii. code.google.com/p/giscloud/wiki/SerializedSpatialIndexes
Jon Bringhurst
Hej @Jon, lepiej byłoby dodać jako odpowiedź. W ten sposób może stać samodzielnie, a zyskasz uznanie, jeśli ludzie myślą, że ma to wartość!
JasonBirch