🚀 go-pugleaf

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

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.

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.

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

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?

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

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?

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

Borneq <borneq@antyspam.hidden.pl> 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.
-- 


----Android NewsGroup Reader----
http://usenet.sinaapp.com/

On Saturday, December 7, 2019 at 5:47:21 AM UTC+1, slawek wrote:
> Borneq <b@a.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

"M.M." <mmarszik@gmail.com> Wrote in message:
> A jakby dopracować ( bo to pomysł nieprzemyślany ) takie indeksowanie, żedajemy ileś dodatkowych losowych punktów i im przypisujemy grupy najbliższychpunktów? Pozdrawiam

Sortowanie sprawdziło się w 3D. Powinno sprawdzić się i w 1024D itd.

Ale ogólnie - jeżeli A jest blisko B, B jest blisko C, to A jest
 blisko C. Tyle że przy n punktach relacji d(P, Q) będzie O(n**2),
 a indeksów posortowanych po współrzędnych przestrzeni k
 wymiarowej O(k*n). Nawet dla k=1024 sortowanie wydaje się
 bardziej opłacalne. Chyba że np. k=1024, n=10. Wtedy policzenie
 brute force to tylko 45 policzyć odległość.


----Android NewsGroup Reader----
http://usenet.sinaapp.com/