Struktura danych dla efektywnego pobierania najbliższego elementu z zestawu

Question

tl; dr Jak można skutecznie wdrożyć coś takiego jak Mathematica?

Mathematica posiada funkcję o nazwie Nearest który odbędzie listę „rzeczy” (mogą być liczbami, koordynuje w n-wymiarowej przestrzeni, sznurki, etc.), a zwróci NearestFunction obiekt. Ten obiekt jest funkcją, która po zastosowaniu do x zwróci element listy, który jest najbliższy x według niektórych metry odległości. Metryka odległości może być przekazana jako parametr do Nearest: domyślnie używa odległości euklidesowej dla danych liczbowych i pewnego rodzaju odległości edycyjnej dla łańcuchów.

---

Przykład (to mamy nadzieję, aby kwestia bardziej jasne)

nf = Nearest[{92, 64, 26, 89, 39, 19, 66, 58, 65, 39}];

nf[50] powróci 58, element najbliżej 50. nf[50, 2] zwróci {58, 39}, dwa najbliższe elementy.

---

Pytanie: Co jest skutecznym sposobem realizacji tej funkcji? Jaki rodzaj struktury danych może być używany wewnętrznie? Jaka jest najlepsza z możliwych złożoność obliczania najbliższego elementu dla różnych typów danych?

Dla zwykłej listy numerów sortowanie ich i wykonywanie wyszukiwania binarnego będzie działało, ale Nearest działa z wielowymiarowymi danymi, jak również z dowolną funkcją odległości, więc przypuszczam, że używa czegoś bardziej ogólnego. Ale nie byłbym zaskoczony, gdyby okazało się, że specjalizuje się w niektórych rodzajach funkcji danych/odległości.

Answer 1

W przypadku dobrze funkcjonujących funkcji odległości istnieje wiele struktur danych zoptymalizowanych specjalnie do tego celu. Dla danych wielowymiarowych, k-d tree (i inne binary space partitioning trees) może dać doskonałe nearest-neighbor searches, zwykle w sublinearnym czasie. Możesz również zajrzeć do metric trees, które są strukturami drzewnymi zoptymalizowanymi do przechowywania punktów w pewnej przestrzeni metrycznej w sposób, który obsługuje wyszukiwania najbliższego sąsiada. W zależności od konkretnej przestrzeni metrycznej (odległość euklidesowa, odległość edycji itp.), Różne struktury danych mogą być mniej lub bardziej odpowiednie.

Dla dowolnych funkcji odległościowych, na których nie ma żadnych ograniczeń w zachowaniu (na przykład nierówności trójkąta, na przykład), najlepsze, co można zrobić, to wyszukiwanie liniowe, ponieważ funkcja odległości może być nieskończona dla wszystkich punkty z wyjątkiem jednego określonego punktu w zestawie.

Mam nadzieję, że to pomoże!

Answer 2

Wszystko zależy od danych i metryki. Przeczytaj o tym tutaj: Nearest Neighbour Search