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

14

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.

Kaustubh Kaluskar
źródło

Odpowiedzi:

9

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,

rchilton1980
źródło
7

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.logN.)N.O(logN.)

dmckee --- były kot moderator
źródło
5

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!

eeismail
źródło
Należy zwrócić uwagę, że długość krawędzi komórki powinna wynosić co najmniej promień wyszukiwania, lub jeśli każda cząstka ma swój własny promień wyszukiwania, wówczas promień maksymalny.
Pedro
Tak jest w przypadku MD; tutaj nie wiemy, jaki jest ten promień a priori .
aeismail
Podobny schemat zastosowano przez długi czas w symulacjach grawitacyjnych chmur cząstek na dużą skalę. Nie wiem, czy jest to nadal stan techniki.
dmckee --- były kot moderator
4

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.

Kwarc
źródło
3

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 wnlog(n) a późniejsze wyszukiwanie najbliższego sąsiada jest liniowe pod względem liczby punktów danych.

Mam nadzieję, że to pomoże!

Dr_Sam
źródło