Re: Wyszukiwanie bliskich punktów w wielowymiarowej przestrzeni

eGospodarka.pl › Grupy › pl.comp.programming › Wyszukiwanie bliskich punktów w wielowymiarowej przestrzeni › Re: Wyszukiwanie bliskich punktów w wielowymiarowej przestrzeni

Path: news-archive.icm.edu.pl!news.icm.edu.pl!newsfeed.pionier.net.pl!3.eu.feeder.erj
e.net!feeder.erje.net!news.roellig-ltd.de!open-news-network.org!border2.nntp.am
s1.giganews.com!nntp.giganews.com!peer01.ams1!peer.ams1.xlned.com!news.xlned.co
m!peer01.fr7!futter-mich.highwinds-media.com!news.highwinds-media.com!newsfeed.
neostrada.pl!unt-exc-02.news.neostrada.pl!unt-spo-b-01.news.neostrada.pl!news.n
eostrada.pl.POSTED!not-for-mail
Subject: Re: Wyszukiwanie bliskich punktów w wielowymiarowej przestrzeni
Newsgroups: pl.comp.programming
References: <5dd48322$0$549$65785112@news.neostrada.pl>
<4...@g...com>
<5dd4db9f$0$17363$65785112@news.neostrada.pl>
<5dd4dbf7$0$17363$65785112@news.neostrada.pl>
<9...@g...com>
<5dd4f071$0$524$65785112@news.neostrada.pl>
<5...@g...com>
From: Borneq <b...@a...hidden.p>
Date: Thu, 21 Nov 2019 19:44:41 +0100
User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:60.0) Gecko/20100101
Thunderbird/60.9.1
MIME-Version: 1.0
In-Reply-To: <5...@g...com>
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Language: pl
Content-Transfer-Encoding: 8bit
Lines: 20
Message-ID: <5dd6db19$0$555$65785112@news.neostrada.pl>
Organization: Telekomunikacja Polska
NNTP-Posting-Host: 91.239.205.59
X-Trace: 1574361881 unt-rea-a-02.news.neostrada.pl 555 91.239.205.59:55064
X-Complaints-To: a...@n...neostrada.pl
X-Received-Bytes: 2275
X-Received-Body-CRC: 2736890658
Xref: news-archive.icm.edu.pl pl.comp.programming:214473
[ ukryj nagłówki ]
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?