Najbliższy punkt do innego punktu na hipersferze

Question

Mam n (około 10^5) punktów na hipersferze o wymiarze m (między 10^4 a 10^6).

Mam zamiar zrobić kilka pytań w formularzu "dany punkt p, znajdź najbliższy n punktów do p". Wykonam około n tych zapytań.

(nie wiem, czy fakt hypersphere pomaga w ogóle.)

Prosty algorytm naiwny, aby rozwiązać ten problem jest dla każdego zapytania, aby porównać p do wszystkich innych punktów n. Wykonanie tego n razy kończy się runtime O (n^2 m), który jest o wiele za duży, abym mógł obliczyć.

Czy istnieje skuteczniejszy algorytm, którego mogę użyć? Gdybym mógł dostać to do O (nm) z pewnymi czynnikami logującymi, które byłyby świetne.

Answer 1

Prawdopodobnie nie. Posiadanie wielu wymiarów sprawia, że ​​sprawne indeksowanie jest niezwykle trudne. Dlatego ludzie szukają możliwości zmniejszenia liczby wymiarów do czegoś, co można kontrolować.

Więcej informacji na temat https://en.wikipedia.org/wiki/Curse_of_dimensionality i https://en.wikipedia.org/wiki/Dimensionality_reduction.

Answer 2

Podziel swoją przestrzeń na hiperszeuby - wywołaj te komórki - z wybranym rozmiarem krawędzi, aby średnio jeden punkt na kostkę miał jeden punkt. Będziesz potrzebował mapy z hiperkomórkami do zestawu punktów, które zawierają.

Następnie, biorąc pod uwagę punkt, sprawdź jego hiperkomórkę pod kątem innych punktów. Jeśli jest pusta, spójrz na sąsiednie hipersześciany (poleciłbym dosłownie hipersześcianę hiperkomórek dla uproszczenia, a nie przybliżenie hiperszfery zbudowanej z hiperkomórek). Sprawdź to dla innych punktów. Powtarzaj, aż uzyskasz punkt. Zakładając, że twoje punkty są losowo rozdzielone, szanse są wysokie, że znajdziesz drugi punkt w ciągu 1-2 rozszerzeń.

Po znalezieniu punktu sprawdź wszystkie hiperkomórki, które mogą zawierać bliższy punkt. Jest to możliwe, ponieważ punkt, który znajdujesz, może znajdować się w rogu, ale jest trochę bliżej hipersześcianu zawierającego wszystkie hiperkomórki, które sprawdziłeś do tej pory.