Powtarzane obliczenia najbliższego sąsiada dla milionów punktów danych za wolno

Mam zestaw danych obejmujący miliony punktów danych w 3D. Aby wykonać obliczenia, muszę obliczyć sąsiada (wyszukiwanie zakresu) dla każdego punktu danych w promieniu, spróbować dopasować funkcję, obliczyć błąd dopasowania, powtórzyć to dla następnego punktu danych i tak dalej. Mój kod działa poprawnie, ale jego uruchomienie zajmuje bardzo dużo czasu, około 1 sekundy na punkt danych! Jest tak prawdopodobnie dlatego, że dla każdego punktu musi przeszukiwać cały zestaw danych. Czy istnieje sposób na szybkie przyspieszenie procesu? Mam pomysł, że jeśli uda mi się w jakiś sposób ustalić relację sąsiedztwa między pierwszymi sąsiadami, może to być mniej powolne. Jeśli to pomaga, staram się znaleźć optymalną szerokość okna Parzen w 3D.

Sugerowałbym googling do ograniczania hierarchii woluminów (w szczególności drzewa BSP). Biorąc pod uwagę chmurę punktów, możesz znaleźć płaszczyznę, która dzieli ją na dwie równe podgrupy. Następnie, gdy musisz znaleźć zbiór punktów, które znajdują się w promieniu R punktu testowego, możesz najpierw porównać swój punkt testowy z tą płaszczyzną, a jeśli jego wysokość jest większa niż R, to cała podgrupa poniżej płaszczyzny musi być również dalej niż R (więc nie musisz sprawdzać żadnego z tych punktów). Możesz zastosować tę ideę także rekurencyjnie, ostatecznie uzyskując n log n złożoności typu n-kwadrat. (To jest BSP / partycjonowanie przestrzeni binarnej,

Istnieje kilka struktur danych do przechowywania danych, które zachowują informacje o pozycji i bliskości; tam, umożliwiając szybkie określenie najbliższego sąsiada (-ów).

W szczególności R drzew (i wyspecjalizowanych formach, takich jak R * -trees ) i X drzew . Wiele opcji zoptymalizowanych pod kątem nieco innych zastosowań.

Wybór drzewa R * zamiast naiwnego wyszukiwania najbliższego sąsiada był dużą częścią mojego uzyskania 10000-krotnego przyspieszenia z konkretnego kodu. (OK, może kilkaset z tego było drzewem R *, większość reszty wynikała z tego, że naiwne wyszukiwanie zostało źle zakodowane, tak że zniszczyło pamięć podręczną. :: westchnienie )

$O(N \log N)$$N$$O(\log N)$

Jest to bardzo podobne do jednego z największych wyzwań w dziedzinie dynamiki molekularnej - obliczenia wszystkich interakcji parami między cząstkami niezwiązanymi.

Tam używamy list komórek (lub list sąsiadów ), aby pomóc nam dowiedzieć się, co jest w pobliżu; w przypadku tej aplikacji lista komórek jest prawdopodobnie łatwiejszym w użyciu algorytmem:

• Podziel pudełko na serię komórek.
• Dla każdej cząstki określ, do której komórki należy ją przypisać (O (1) na cząsteczkę).
• Następnie dla każdej cząstki sprawdź „własną” komórkę plus sąsiednie komórki; jeśli którykolwiek z nich jest zajęty, dalsze wyszukiwanie nie jest konieczne.
• Jeśli wszyscy najbliżsi sąsiedzi są pusti, rozwijaj się do najbliższych sąsiadów i tak dalej, aż do znalezienia cząstki.

Jeśli twój system ma mniej więcej równomierny rozkład cząstek, znacznie zmniejszy to koszt twojego algorytmu, zgodnie z grubością siatki. Konieczne jest jednak pewne dostrajanie: zbyt gruba siatka i nie zaoszczędzisz dużo czasu; zbyt dobrze, a spędzasz dużo czasu na jeżdżeniu po pustych komórkach siatki!

Zdecydowanie powinieneś sprawdzić drzewa i oktawy KD, które są metodami wyboru dla zestawów punktów (podczas gdy BSP są dla obiektów ogólnych, a siatki dla mniej lub bardziej jednolitych gęstości). Mogą być bardzo kompaktowe i szybkie, minimalizując obciążenie zarówno pamięci, jak i obliczeń, i są łatwe do wdrożenia.

Kiedy punkty są mniej więcej równomiernie rozmieszczone (nawet z pustymi obszarami, ale nie może występować osobliwość gęstości lub inna wysoka koncentracja), sprawdź wypełnienia kul, jeśli chcesz wypróbować podobną do siatki niehierarchiczną podział przestrzeni.

Prawdopodobnie powinieneś rozważyć budowę triangulacji Delaunaya (no cóż, jej analogu 3D). W 2D jest to specjalna triangulacja punktów danych, która zawsze zawiera najbliższego sąsiada. To samo dotyczy 3D, ale z czworościanami.

Możesz zbudować raz na zawsze triangulację, a następnie wyszukać najbliższego sąsiada bezpośrednio w triangulacji. Myślę, że istnieją pewne dobre algorytmy do zbudowania triangulacji: w 2D, konstrukcja triangulacji jest w$n \log(n)$ a późniejsze wyszukiwanie najbliższego sąsiada jest liniowe pod względem liczby punktów danych.

Mam nadzieję, że to pomoże!