Zrozumienie przechowywania lokalizacji i algorytmów zapytań?

Jednym z najważniejszych aspektów bazy danych wyposażonej w GIS jest możliwość szybkiego wyszukiwania wszystkich punktów w dowolnym dowolnym obszarze geograficznym spełniającym dodatkowe kryteria. (Np. „Znajdź mi najbliższe 3 restauracje do tego miejsca na mapie.”)

Czy ktoś może wskazać mi teoretyczną dyskusję na temat algorytmów? Chcę się dowiedzieć, jak działają.

Ostatecznie chcę zastosować tę samą zdolność do uogólnionych zestawów danych liczbowych - dużej chmury punktów w dowolnej, n-wymiarowej, nie-euklidesowej przestrzeni. Na przykład twarz osoby można scharakteryzować jako wektor liczb: [odległość między oczami, odległość od oka do ust, szerokość twarzy, długość twarzy itp.]. Chcę sfilmować ruch na chodniku, oszacować cechy twarzy każdej osoby, a następnie móc później zapytać o dane, np. „Biorąc pod uwagę twarz tej osoby, znajdź mi 100 najbardziej podobnych twarzy”.

Czy istnieje obecnie oprogramowanie, które umożliwia przeszukiwanie tych uogólnionych przestrzeni?

Dobre opisy algorytmów w 2 i 3 wymiarach pojawiają się w klasycznym tekście autorstwa Prepata i Shamos . Algorytmy stosowane w GIS są specjalnością Hanana Sameta , który opublikował kilka książek na ten temat.

Wyszukiwania w wyższych wymiarach są zwykle wspomagane lub przyspieszane za pomocą wstępnej eksploracji danych, grupowania lub technik zmniejszania wymiarów. Jest to bardziej kwestia analizy danych i statystyk, a nie GIS, który ze swej natury koncentruje się na poszukiwaniach w jednym z czterech wymiarów euklidesowych. Aby uzyskać więcej informacji, wyszukaj na naszym siostrzanym forum stats.stackexchange.com prawdopodobne terminy, takie jak grupowanie , redukcja wymiarowości i skalowanie wielowymiarowe, oraz mniej oczywiste, takie jak pca (analiza głównych komponentów) i svm (maszyny wektorów pomocniczych). To także dobre miejsce, aby zapytać o istniejące oprogramowanie.

Klasyczną odpowiedzią (paleogeograf) jest użycie drzewa KD do przechowywania danych (patrz http://en.wikipedia.org/wiki/Kd-tree ). Działa to z grubsza o połowę danych na dwie partycje w każdym wymiarze po kolei podczas przesuwania się w dół drzewa. Ich zaletą jest to, że po znalezieniu najbliższego elementu możesz także utworzyć listę najbliższych przedmiotów bez dodatkowych kosztów, więc znalezienie trzech najbliższych restauracji jest tak proste, jak znalezienie najbliższego.

Czytałem gdzieś, że eHarmony używa drzew KD do znajdowania „zgodnych dopasowań” w 14 wymiarach.

Słyszałem, że Netezza wdrożyła kilka innowacyjnych algorytmów równoległego przetwarzania przestrzennego . Dokument jest tutaj .

Architektura asymetrycznego przetwarzania masowo równoległego Netezza zapewnia najlepszą kombinację symetrycznego przetwarzania wieloprocesorowego (SMP) i przetwarzania masowo równoległego (MPP), ułatwiając terascale, złożone przetwarzanie zapytań zarówno danych przestrzennych, jak i nieprzestrzennych, bez złożoności, strojenia i agregacji niezbędnych w tradycyjnych systemach.

Aktualizacja

Zapomniałem wspomnieć, że Netezza mocno wykorzystuje twierdzenie Bayesa . Oto kolekcja filmów tutaj .