Przepraszamy, ale to nie jest odpowiedź SQL, ale sposób na uzyskanie przewidywalnej wydajności przy założeniu pewnych ograniczeń danych.
Jak często zmieniają się dane? Jeśli to możliwe, czy możesz wstępnie obliczyć wykres każdej jednostki 5 najbliższych sąsiadów i użyć go do przyspieszenia wyboru?
Jeśli te dane są w większości tylko do odczytu, to...
Jak równomiernie rozłożone są te punkty? Jeśli rozkład jest dość równomierny i dobrze poznany, możesz stworzyć własne mapowanie przestrzenne, umieszczając każdą współrzędną i indeks w tablicy mieszającej.
Jeśli nie potrzebujesz mieć danych w bazie danych, przenieś je do pliku mapowanego w pamięci, aby szybko wyszukiwać skróty. (70-milimetrowe rekordy powinny z łatwością zmieścić się w pamięci).
Używam tej architektury do generowania wyszukiwań poniżej milisekund dla reklam displayowych i trafności dla wyszukiwarek.
==Opracowanie==
Po prostu tworzysz siatkę kwadratów o stałym rozmiarze (jak szachownica) i mapujesz każdy punkt na siatkę i tworzysz listę obiektów, które należą do każdego z pól siatki - jeśli dostosujesz rozmiar każdego poprawnie, powinieneś mieć średnio 5-50 punktów w każdym kwadracie -- jest to w zasadzie drzewo czwórkowe, ale bez drzewa dla uproszczenia.
Dla każdego zasobnika, który jest pusty po rozproszeniu wszystkich danych w zasobnikach, dodajesz informacje o najbliższych zasobnikach zawierających dane.
Teraz możesz ponumerować każdy zasobnik od lewej do prawej-wiersz-ny-wiersz, tak aby każdy zasobnik miał unikalny numer, który można obliczyć na podstawie współrzędnych -- i wstawiasz każdy zasobnik do tabeli mieszającej lub, jeśli pozwala na to miejsce, tak samo prosta tabela przeglądowa.
Teraz, gdy masz zapytanie, po prostu oblicz, do którego zasobnika zostanie odwzorowane, a otrzymasz albo listę obiektów w tym zasobniku, albo otrzymasz „pusty” zasobnik, który zawiera wskaźniki do najbliższego zasobnika, który ma zawartość .
To da ci pierwszą listę kandydatów, których szukasz, a teraz po prostu musisz biec i zobaczyć, który z nich jest najbliżej.
W 99% przypadków tak by było – ale jeśli martwisz się, że (a) w następnych wiaderkach, które są w rzeczywistości bliżej, znajdują się kondydaty, po prostu sprawdź 8 sąsiednich wiader i zobacz, czy możesz znajdź tam bliżej.
Jeśli teraz chcesz również uzyskać listę wszystkich obiektów, które są najbliżej, oblicz również prostą sieć 5 najbliższych sąsiadów dla każdego obiektu, dzięki czemu uzyskasz strukturę danych taką jak A->{B,C,D ,E,F}, B->{A,D,G,H,I}, C->{A,J,K,G,M}....
Utworzy to prostą sieć, którą możesz teraz przemierzać za pomocą odmiany Dijkstra tutaj, aby uzyskać wszystkie punkty sąsiadujące z najbliższym punktem.
Budowanie struktur danych zajmie trochę czasu, ale po wykonaniu i prawidłowym wyszukaniu i zwróceniu zestawu danych można wykonać mniej niż milisekundy (nie licząc żadnej przyczyny komunikacji http lub off-box)
Mam nadzieję, że to pomoże.
