Mam szukać wielokrotnie, nie identycznych a podobnych, coś takiego jak
wyszukiwanie podobnego obrazu czy odcisku palca bez konieczność
przeszukania całości czy nawet znacznej części całości.
Gdy mam przypadek 1D to najpierw sortuję.
Dla 2D mogę zrobić boksy wystarczająco duże by nie było marnotrawstwa na
boksy nie zawierające żadnych elementów , te boksy mają podboksy a te
elementy.

Jest problem, bo gdy szerokość to 100, wtedy
szukając 401 mogę znaleźć 490 a nie znajdę bliskiego 399.
Trzeba by szukać w boksach naokoło, w 9 zamiast w jednym. To jeszcze się
da, ale dla 3D będzie to 27, ogólnie 3^n, co gdy mamy 512D?

do góry

On Wednesday, November 20, 2019 at 1:04:51 AM UTC+1, Borneq wrote:
> Mam szukać wielokrotnie, nie identycznych a podobnych, coś takiego jak
> wyszukiwanie podobnego obrazu czy odcisku palca bez konieczność
> przeszukania całości czy nawet znacznej części całości.
> Gdy mam przypadek 1D to najpierw sortuję.
> Dla 2D mogę zrobić boksy wystarczająco duże by nie było marnotrawstwa na
> boksy nie zawierające żadnych elementów , te boksy mają podboksy a te
> elementy.
>
> Jest problem, bo gdy szerokość to 100, wtedy
> szukając 401 mogę znaleźć 490 a nie znajdę bliskiego 399.
> Trzeba by szukać w boksach naokoło, w 9 zamiast w jednym. To jeszcze się
> da, ale dla 3D będzie to 27, ogólnie 3^n, co gdy mamy 512D?

Jakie wejście i jakie wyjście programu?

Pozdrawiam

do góry

W dniu 20.11.2019 o 04:03, M.M. pisze:
> Jakie wejście i jakie wyjście programu?
>
> Pozdrawiam
>

Wejście, dwa zbiory A(p1,p2...pn) B(q1.q2...qm)
gdzie pi, qk - to punktu o tym samym wymiarze

Wyjście:
punkty zbioru A gdzie dla jednego pi mamy podaną listę być może pustą
iluś punktów ze zbioru B, które są w odległości co najwyżej epsilon,
odległość może być różnie liczona, chyba że algorytm wymaga by była
konkretnie np. jako suma po współrzędnych czy maksymalna współrzędna.

do góry

W dniu 20.11.2019 o 07:22, Borneq pisze:
> odległość może być różnie liczona, chyba że algorytm wymaga by była
> konkretnie np. jako suma po współrzędnych czy maksymalna współrzędna.


To znaczy sua po różnicy współrzędnych albo maksymalna różnica
współrzędnych.

do góry

On Wednesday, November 20, 2019 at 7:23:53 AM UTC+1, Borneq wrote:
> W dniu 20.11.2019 o 07:22, Borneq pisze:
> > odległość może być różnie liczona, chyba że algorytm wymaga by była
> > konkretnie np. jako suma po współrzędnych czy maksymalna współrzędna.
>
>
> To znaczy sua po różnicy współrzędnych albo maksymalna różnica
> współrzędnych.

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.

Pozdrawiam

do góry

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?

do góry

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

do góry

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?

do góry

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

do góry

On Saturday, December 7, 2019 at 5:47:21 AM UTC+1, slawek wrote:
> Borneq <...@...h.p> Wrote in message:
> > Mam szukać wielokrotnie, nie identycznych a podobnych, coś takiego jak
wyszukiwanie podobnego obrazu czy odcisku palca bez konieczność przeszukania całości
czy nawet znacznej części całości.Gdy mam przypadek 1D to najpierw sortuję.Dla 2D
mogę zrobić boksy wystarczająco duże by nie było marnotrawstwa na boksy nie
zawierające żadnych elementów , te boksy mają podboksy a te elementy.Jest problem, bo
gdy szerokość to 100, wtedyszukając 401 mogę znaleźć 490 a nie znajdę bliskiego
399.Trzeba by szukać w boksach naokoło, w 9 zamiast w jednym. To jeszcze się da, ale
dla 3D będzie to 27, ogólnie 3^n, co gdy mamy 512D?
>
> W 2D sortuj po x i po y, czyli 2*1D. Punkty bliskie w 2D są też
> bliskie po x i po y. Przejdź do nD: będzie n sortowań. Czyli 512
> sortowań. Szukasz sąsiadów, masz ich jakieś 2*512, z sąsiadów
> wybierasz najbliższego. Jak chcesz mieć m najbliższych bierzesz
> 2*m*n sąsiadów. Co powinno być wykonalne.

A jakby dopracować ( bo to pomysł nieprzemyślany ) takie indeksowanie, że
dajemy ileś dodatkowych losowych punktów i im przypisujemy grupy najbliższych
punktów?

Pozdrawiam

do góry