Sergei-
Thanks for responding.
On 4/12/06, Sergei Golubchik <serg@stripped> wrote:
> Hi!
>
> On Apr 11, JJ Tavernier wrote:
> > Hi, I'd like to add a k-Nearest Neighbor functionality to mysql for
> > spatial data. I'm thinking that the usage will look something like
> > this:
> >
> > CREATE TABLE geom2 (g GEOMETRY);
> >
> > // ... insert some data
> >
> > SET @g = GeomFromText('POINT(1 1)');
> > SELECT k_nearest_neighbor(@g, 3) FROM geom2;
>
> It would be probably very slow without a special index.
> R-tree was not designed for this kind of task.
It's my understanding that k-NN can be implemented efficiently with
R-Trees. This paper gives one algorithm:
http://citeseer.ist.psu.edu/roussopoulos95nearest.html. This paper
gives another: http://www.cs.umd.edu/~hjs/pubs/incnear2.pdf.
>
> > The k_nearest_neighbor would then return the three closest objects to
> > the point (1,1). From the portion of the manual on user-defined
> > functions (http://dev.mysql.com/doc/refman/5.0/en/adding-udf.html), it
> > looks like only strings, ints and reals can be returned from
> > functions. How would I go about returning a row from a spatially
> > indexed table? How do I deal with returning multiple rows? Am I wrong
> > in thinking that functions are the way to go about solving this? I'm
> > very new to mysql development, so I would not be surprised if this is
> > the case.
>
> You cannot do it with an udf. Better to change the syntax to
>
> SELECT * FROM geom2 WHERE k_nearest_neighbor(geom2.geom_col, @g, 3)
>
> or
>
> SELECT * FROM geom2 WHERE k_nearest_neighbor(geom2.geom_col, @g) <= 3
>
> This could be done with an udf.
>
> But unless you have a special index for that (SS-tree, perhaps ?),
> there's no need to code a function in C, you can write an SQL stored
> function - most time consuming part is table scans, not interpreting the
> language.
R-tree can be traversed efficiently to find kNN, so I'd like to use
the efficient algorithms (in papers above) instead of using full-table
scans. If UDFs cannot be used to query the k-NN of a given object,
what other options are available to me within mysql to return multiple
rows .
Thanks,
JJ
