On Thursday, November 21, 2019 at 7:44:43 PM UTC+1, Borneq wrote:
> W dniu 21.11.2019 o 01:13, M.M. pisze:
> > On Wednesday, November 20, 2019 at 8:51:33 AM UTC+1, Borneq wrote:
> >> W dniu 20.11.2019 o 07:37, M.M. pisze:
> >>> Trzeba przeiterować i policzyć, albo najpierw zaindeksować czymś w okolicach
> >>> kd-tree. Można posłużyć się bazą danych, np. postgres ma indeksy do tego
> >>> celu, działa dobrze na ogromnych zbiorach danych.
> >>
> >> Bardziej chodzi mi o algorytm, czyli kd-tree?
> >
> > Jeśli chcesz zaindeksować przed wyszukiwaniem, to można próbować kd-tree.
> > Ale nie tylko, może pomysł z gridem być lepszy.
> >
> > Pozdrawiam
> >
>
> Grid sprawdza się dla małej wymiarowości,
> mam grid co 100, mam punkt 401, znajduję 490, ale nie mogę znależć już
> 399 choć jest bliżej,
> więc trzeba by naokoło, zamiast jednego boxa -9!
> Dla dwóch wymiarów, a dla trzech 26, ogólnie 3^n, co z kilkuset?

Stosuje się też techniki zmniejszania wymiarów. W przypadku odcisków
palców np. zlicza ilość charakterystycznych wzorów.

Jeśli wymiarów jest dużo, np. 100 i ma być gęste wypełnienie w każdym
wymiarze, to potrzeba M^100 elementów, gdzie M jest duże, ma wartość
chociaż 10 :) Nie wiem jak kd-tree się sprawdzi dla dużej wymiarowości.
By trzeba sprawdzić, albo poczytać.

Tam piszą też że się nie nadają:
https://stackoverflow.com/questions/37132774/why-k-d
-trees-is-not-used-for-high-dimensional-data

Pozdrawiam