Thread Subject: Please Help. Newbie. Many Nearest Neighbour question.

Forgive my ignorance please, but I searched for about 2 hours and was unable to locate an answer to simple question (newbie).

I have a large set of lat/lon coordinates (> 800K). Each record is either of type 'A', or 'B' the majority (> 70% are 'B'). I am trying to find the nearest 'B' for every 'A'. Now I know this has to be rather simple, whether with ANN or the K-nearest script.

I am a little concerned with the size of the data (number of records) and was wondering if there were a simple way to do this - like I'm 5 simple. - thanks

bo

Bo,

    If you have MATLAB R2009a
help DelaunayTri/nearestNeighbor

If you have an earlier version
help dsearch

We have tried to make the function name more meaningful in the new
DelaunayTri class.

Best regards,

Damian


"Bo " <bo.coughlin@aonfg.com> wrote in message
news:gv3iv7$8te$1@fred.mathworks.com...
> Forgive my ignorance please, but I searched for about 2 hours and was
> unable to locate an answer to simple question (newbie).
>
> I have a large set of lat/lon coordinates (> 800K). Each record is either
> of type 'A', or 'B' the majority (> 70% are 'B'). I am trying to find the
> nearest 'B' for every 'A'. Now I know this has to be rather simple,
> whether with ANN or the K-nearest script.
>
> I am a little concerned with the size of the data (number of records) and
> was wondering if there were a simple way to do this - like I'm 5 simple. -
> thanks
>
> bo

Try this:

% Data
FoodStore=randn(10,2);
MobileRobots=randn(30,2);

% Engine
Stock = size(FoodStore,1);
[WallMarkSuperMall Where] = unique(FoodStore, 'rows');
if Stock > size(WallMarkSuperMall,1)
    warning('Duplicated FoodStore');
end

Garden = delaunay(WallMarkSuperMall(:,1),WallMarkSuperMall(:,2));

ImportantAddress = dsearch(WallMarkSuperMall(:,1),WallMarkSuperMall(:,2),Garden,...
                           MobileRobots(:,1),MobileRobots(:,2));

ImportantAddress = Where(ImportantAddress);

% Check
figure(1);
clf
hold on
axis equal
plot(FoodStore(:,1),FoodStore(:,2),'or')
plot(MobileRobots(:,1),MobileRobots(:,2),'b.')
for k=1:length(ImportantAddress)
    plot([MobileRobots(k,1) FoodStore(ImportantAddress(k),1)],...
         [MobileRobots(k,2) FoodStore(ImportantAddress(k),2)],'b')
end
voronoi(FoodStore(:,1),FoodStore(:,2),'k');

% Bruno

I have a couple of questions...
1. Can the nearest neighbors be repeated? In other words, can b(1) be the nearest neighbor to 2 A elements (e.g. a(1) and a(2))? If not, the problem gets a little more complicated and you'd need some sort of assignment algorithm (e.g., Munkres, Auction)
2. What are you trying to simplify? The conversion of lat/long to distance, or the determination of the nearest neighbor? The latter will depend on the answer to (1) above.
-TravisC

"Bo " <bo.coughlin@aonfg.com> wrote in message <gv3iv7$8te$1@fred.mathworks.com>...
> Forgive my ignorance please, but I searched for about 2 hours and was unable to locate an answer to simple question (newbie).
>
> I have a large set of lat/lon coordinates (> 800K). Each record is either of type 'A', or 'B' the majority (> 70% are 'B'). I am trying to find the nearest 'B' for every 'A'. Now I know this has to be rather simple, whether with ANN or the K-nearest script.
>
> I am a little concerned with the size of the data (number of records) and was wondering if there were a simple way to do this - like I'm 5 simple. - thanks
>
> bo

"Bo " <bo.coughlin@aonfg.com> wrote in message <gv3iv7$8te$1@fred.mathworks.com>...
> Forgive my ignorance please, but I searched for about 2 hours and was unable to locate an answer to simple question (newbie).
>
> I have a large set of lat/lon coordinates (> 800K). Each record is either of type 'A', or 'B' the majority (> 70% are 'B'). I am trying to find the nearest 'B' for every 'A'. Now I know this has to be rather simple, whether with ANN or the K-nearest script.
>
> I am a little concerned with the size of the data (number of records) and was wondering if there were a simple way to do this - like I'm 5 simple. - thanks
>
> bo

It is not clear to me what your problem is, anyway this may help

http://www.mathworks.com/matlabcentral/fileexchange/22190

http://giaccariluigi.altervista.org/blog/

"Luigi Giaccari" <giaccariluigi@msn.com> wrote in message <gv469v$c6i$1@fred.mathworks.com>...
> "Bo " <bo.coughlin@aonfg.com> wrote in message <gv3iv7$8te$1@fred.mathworks.com>...
> > Forgive my ignorance please, but I searched for about 2 hours and was unable to locate an answer to simple question (newbie).
> >
> > I have a large set of lat/lon coordinates (> 800K). Each record is either of type 'A', or 'B' the majority (> 70% are 'B'). I am trying to find the nearest 'B' for every 'A'. Now I know this has to be rather simple, whether with ANN or the K-nearest script.
> >
> > I am a little concerned with the size of the data (number of records) and was wondering if there were a simple way to do this - like I'm 5 simple. - thanks
> >
> > bo
>
> It is not clear to me what your problem is, anyway this may help
>
> http://www.mathworks.com/matlabcentral/fileexchange/22190

I tried to the above FEX with 10^4 points for A and B (OP's problem size is 10^5 A+B) and it crashes my Matlab (2009A + Vista 32).

It takes 0.8 second using Delaunay for (10^4)^2 points and 12.5 seconds for (10^5) points.

Bruno

This crashes:

% Data
FoodStore=randn(1e4,2);
MobileRobots=randn(1e4,2);

tic
ptrtree=BuildGLTree(FoodStore(:,1),FoodStore(:,2));
NNG=NNSearch(FoodStore(:,1),FoodStore(:,2),...
             MobileRobots(:,1),MobileRobots(:,2),ptrtree);
toc

% Bruno

Should read:

>
> It takes 0.8 second using Delaunay for (10^4) x 2 points and 12.5 seconds for (10^5) x 2 points.

 

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <gv4905$1eb$1@fred.mathworks.com>...
> This crashes:
>
> % Data
> FoodStore=randn(1e4,2);
> MobileRobots=randn(1e4,2);
>
> tic
> ptrtree=BuildGLTree(FoodStore(:,1),FoodStore(:,2));
> NNG=NNSearch(FoodStore(:,1),FoodStore(:,2),...
> MobileRobots(:,1),MobileRobots(:,2),ptrtree);
> toc
>
> % Bruno


HI Bruno I just noticed your post about crash of my algorithm.

I never tried on Vista but that's the first time I heard problem like yours.

Can you kindly send a report to my e-mail (giaccariluigi@msn.com) with all possible informations. Thank you in advance.

Anyway for 1e5 points it should take about 0,1 seconds (if points are not too sparse).

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <gv493t$8o7$1@fred.mathworks.com>...
> Should read:
>
> >
> > It takes 0.8 second using Delaunay for (10^4) x 2 points and 12.5 seconds for (10^5) x 2 points.
>
>


Bruno was right, I thing I made a mess in the last update, e re-uploaded version is on the way. Sorry

Luigi sent me a bug corrected version of his code, it works great: given the same result as Delaunay for random or sorted lists u to 10^5 elements. It is impressively fast.

Bruno

On May 21, 10:55 am, "Bruno Luong" <b.lu...@fogale.findmycountry>
wrote:
> Try this:
>
> % Data
> FoodStore=randn(10,2);
> MobileRobots=randn(30,2);
>
> % Engine
> Stock = size(FoodStore,1);
> [WallMarkSuperMall Where] = unique(FoodStore, 'rows');
> if Stock > size(WallMarkSuperMall,1)
>     warning('Duplicated FoodStore');
> end
>
> Garden = delaunay(WallMarkSuperMall(:,1),WallMarkSuperMall(:,2));
>
> ImportantAddress = dsearch(WallMarkSuperMall(:,1),WallMarkSuperMall(:,2),Garden,...
>                            MobileRobots(:,1),MobileRobots(:,2));
>
> ImportantAddress = Where(ImportantAddress);
>
> % Check
> figure(1);
> clf
> hold on
> axis equal
> plot(FoodStore(:,1),FoodStore(:,2),'or')
> plot(MobileRobots(:,1),MobileRobots(:,2),'b.')
> for k=1:length(ImportantAddress)
>     plot([MobileRobots(k,1) FoodStore(ImportantAddress(k),1)],...
>          [MobileRobots(k,2) FoodStore(ImportantAddress(k),2)],'b')
> end
> voronoi(FoodStore(:,1),FoodStore(:,2),'k');
>
> % Bruno

Nice example ... thanks

TH

http://dsp-system-design.blogspot.com/