Horton

Thread

  1. k-neighbourhood search in databases

    Oleg Bartunov <oleg@sai.msu.su> — 2011-04-08T12:21:50Z

    Hi there,

I'm interesting if other databases provides built-in effective 
knn search ? Google didn't help me.

 	Regards,
 		Oleg
_____________________________________________________________
Oleg Bartunov, Research Scientist, Head of AstroNet (www.astronet.ru),
Sternberg Astronomical Institute, Moscow University, Russia
Internet: oleg@sai.msu.su, http://www.sai.msu.su/~megera/
phone: +007(495)939-16-83, +007(495)939-23-83

  2. Re: k-neighbourhood search in databases

    Hans-Jürgen Schönig <postgres@cybertec.at> — 2011-04-08T12:44:32Z

    hello ...

i have put some research into that some time ago and as far as i have seen there is a 99% chance that no other database can do it the way we do it. it seems nobody comes even close to it (especially not in the flexibility-arena).

oracle: disgusting workaround ...
http://www.orafaq.com/usenet/comp.databases.oracle.misc/2005/11/03/0083.htm

db2: disgusting workaround (no server side code it seems)

sybase: disgusting workaround (no serverside code it seems)

microsoft: there seems to be something coming out (or just out) but i have not seen anything working yet.

	regards,

		hans



On Apr 8, 2011, at 2:21 PM, Oleg Bartunov wrote:

> Hi there,
> 
> I'm interesting if other databases provides built-in effective knn search ? Google didn't help me.
> 
> 	Regards,
> 		Oleg
> _____________________________________________________________
> Oleg Bartunov, Research Scientist, Head of AstroNet (www.astronet.ru),
> Sternberg Astronomical Institute, Moscow University, Russia
> Internet: oleg@sai.msu.su, http://www.sai.msu.su/~megera/
> phone: +007(495)939-16-83, +007(495)939-23-83
> 
> -- 
> Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
> To make changes to your subscription:
> http://www.postgresql.org/mailpref/pgsql-hackers
> 

--
Cybertec Schönig & Schönig GmbH
Gröhrmühlgasse 26
A-2700 Wiener Neustadt, Austria
Web: http://www.postgresql-support.de

  3. Re: k-neighbourhood search in databases

    Oleg Bartunov <oleg@sai.msu.su> — 2011-04-08T13:24:51Z

    Hans,

thanks a lot. I've heard about Oracle Spatial, but I don't know
if it's knn is  just syntactic sugar for workarounds.

Oleg

On Fri, 8 Apr 2011, PostgreSQL - Hans-J?rgen Sch?nig wrote:

> hello ...
>
> i have put some research into that some time ago and as far as i have seen there is a 99% chance that no other database can do it the way we do it. it seems nobody comes even close to it (especially not in the flexibility-arena).
>
> oracle: disgusting workaround ...
> http://www.orafaq.com/usenet/comp.databases.oracle.misc/2005/11/03/0083.htm
>
> db2: disgusting workaround (no server side code it seems)
>
> sybase: disgusting workaround (no serverside code it seems)
>
> microsoft: there seems to be something coming out (or just out) but i have not seen anything working yet.
>
> 	regards,
>
> 		hans
>
>
>
> On Apr 8, 2011, at 2:21 PM, Oleg Bartunov wrote:
>
>> Hi there,
>>
>> I'm interesting if other databases provides built-in effective knn search ? Google didn't help me.
>>
>> 	Regards,
>> 		Oleg
>> _____________________________________________________________
>> Oleg Bartunov, Research Scientist, Head of AstroNet (www.astronet.ru),
>> Sternberg Astronomical Institute, Moscow University, Russia
>> Internet: oleg@sai.msu.su, http://www.sai.msu.su/~megera/
>> phone: +007(495)939-16-83, +007(495)939-23-83
>>
>> --
>> Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
>> To make changes to your subscription:
>> http://www.postgresql.org/mailpref/pgsql-hackers
>>
>
> --
> Cybertec Sch?nig & Sch?nig GmbH
> Gr?hrm?hlgasse 26
> A-2700 Wiener Neustadt, Austria
> Web: http://www.postgresql-support.de
>

 	Regards,
 		Oleg
_____________________________________________________________
Oleg Bartunov, Research Scientist, Head of AstroNet (www.astronet.ru),
Sternberg Astronomical Institute, Moscow University, Russia
Internet: oleg@sai.msu.su, http://www.sai.msu.su/~megera/
phone: +007(495)939-16-83, +007(495)939-23-83

  4. Re: k-neighbourhood search in databases

    Josh Berkus <josh@agliodbs.com> — 2011-04-08T19:58:47Z

    On 4/8/11 5:21 AM, Oleg Bartunov wrote:
> Hi there,
> 
> I'm interesting if other databases provides built-in effective knn
> search ? Google didn't help me.

Nobody I've talked to, and I asked both Couch and Oracle devs.

-- 
Josh Berkus
PostgreSQL Experts Inc.
http://pgexperts.com

  5. Re: k-neighbourhood search in databases

    Oleg Bartunov <oleg@sai.msu.su> — 2011-04-09T03:38:23Z

    On Fri, 8 Apr 2011, Josh Berkus wrote:

> On 4/8/11 5:21 AM, Oleg Bartunov wrote:
>> Hi there,
>>
>> I'm interesting if other databases provides built-in effective knn
>> search ? Google didn't help me.
>
> Nobody I've talked to, and I asked both Couch and Oracle devs.

That's great to know :)

 	Regards,
 		Oleg
_____________________________________________________________
Oleg Bartunov, Research Scientist, Head of AstroNet (www.astronet.ru),
Sternberg Astronomical Institute, Moscow University, Russia
Internet: oleg@sai.msu.su, http://www.sai.msu.su/~megera/
phone: +007(495)939-16-83, +007(495)939-23-83

  6. Re: k-neighbourhood search in databases

    Jeremiah Peschka <jeremiah.peschka@gmail.com> — 2011-04-09T04:39:14Z

    On 4/8/11 5:21 AM, Oleg Bartunov wrote:
> Hi there,
> 
> I'm interesting if other databases provides built-in effective knn
> search ? Google didn't help me.
SQL Server provides some knn search functionality[1] with enhancements coming this November in SQL 11[2].

[1]: http://blogs.msdn.com/b/isaac/archive/2008/10/23/nearest-neighbors.aspx
[2]: http://www.sqlskills.com/BLOGS/BOBB/post/The-nearest-neighbor-optimization-in-SQL-Server-Denali.aspx


-- 
Jeremiah Peschka
Microsoft SQL Server MVP
MCITP: Database Developer, DBA

  7. Re: k-neighbourhood search in databases

    Oleg Bartunov <oleg@sai.msu.su> — 2011-04-10T10:18:14Z

    Wow, custom solution for 2008 still much faster Denali 2011  solution.
Also, what's about not spatial data types ? 
In our approach, we can provide knn for any datatype, which has GiST index 
and distance method.

Oleg
On Fri, 8 Apr 2011, Jeremiah Peschka wrote:

>
> On 4/8/11 5:21 AM, Oleg Bartunov wrote:
>> Hi there,
>>
>> I'm interesting if other databases provides built-in effective knn
>> search ? Google didn't help me.
> SQL Server provides some knn search functionality[1] with enhancements coming this November in SQL 11[2].
>
> [1]: http://blogs.msdn.com/b/isaac/archive/2008/10/23/nearest-neighbors.aspx
> [2]: http://www.sqlskills.com/BLOGS/BOBB/post/The-nearest-neighbor-optimization-in-SQL-Server-Denali.aspx
>
>
>

 	Regards,
 		Oleg
_____________________________________________________________
Oleg Bartunov, Research Scientist, Head of AstroNet (www.astronet.ru),
Sternberg Astronomical Institute, Moscow University, Russia
Internet: oleg@sai.msu.su, http://www.sai.msu.su/~megera/
phone: +007(495)939-16-83, +007(495)939-23-83

  8. Re: k-neighbourhood search in databases

    Jesper Krogh <jesper@krogh.cc> — 2011-04-10T14:24:54Z

    On 2011-04-10 12:18, Oleg Bartunov wrote:
> Wow, custom solution for 2008 still much faster Denali 2011  solution.
> Also, what's about not spatial data types ? In our approach, we can 
> provide 
> knn for any datatype, which has GiST index and distance method.

Can you share some insight about how it would
work if the distance method is "expensive" (as in 100ms)?

-- 
Jesper

  9. Re: k-neighbourhood search in databases

    Oleg Bartunov <oleg@sai.msu.su> — 2011-04-10T17:45:12Z

    On Sun, 10 Apr 2011, Jesper Krogh wrote:

> On 2011-04-10 12:18, Oleg Bartunov wrote:
>> Wow, custom solution for 2008 still much faster Denali 2011  solution.
>> Also, what's about not spatial data types ? In our approach, we can provide 
>> knn for any datatype, which has GiST index and distance method.
>
> Can you share some insight about how it would
> work if the distance method is "expensive" (as in 100ms)?

I don't understand how does your question connected with my statement :)

Slow distance calculation affects gist-based ordered heap output  as well as
seqscan output from heap, but in the first case you need to calculate just a
few distances (something like height of gist tree), while in the naive way 
one have to calculate n^2 distances.

 	Regards,
 		Oleg
_____________________________________________________________
Oleg Bartunov, Research Scientist, Head of AstroNet (www.astronet.ru),
Sternberg Astronomical Institute, Moscow University, Russia
Internet: oleg@sai.msu.su, http://www.sai.msu.su/~megera/
phone: +007(495)939-16-83, +007(495)939-23-83

  10. Re: k-neighbourhood search in databases

    Jeremiah Peschka <jeremiah.peschka@gmail.com> — 2011-04-10T22:54:03Z

    On Sunday, April 10, 2011 at 3:18 AM, Oleg Bartunov wrote:
Wow, custom solution for 2008 still much faster Denali 2011 solution.
> Also, what's about not spatial data types ? 
> In our approach, we can provide knn for any datatype, which has GiST index 
> and distance method.
> 

There are a number of workarounds (custom data types, mainly) that can be done in SQL Server, but the spatial datatypes themselves are .NET datatypes that ship with SQL Server and I'm pretty sure the methods will only work with the spatial types. The other types are the usual primitives that we all know and love and won't respond to .NET method invocation in the database.

-- 
Jeremiah Peschka
Microsoft SQL Server MVP
MCITP: Database Developer, DBA

> Oleg
> On Fri, 8 Apr 2011, Jeremiah Peschka wrote:
> 
> > 
> > On 4/8/11 5:21 AM, Oleg Bartunov wrote:
> > > Hi there,
> > > 
> > > I'm interesting if other databases provides built-in effective knn
> > > search ? Google didn't help me.
> > SQL Server provides some knn search functionality[1] with enhancements coming this November in SQL 11[2].
> > 
> > [1]: http://blogs.msdn.com/b/isaac/archive/2008/10/23/nearest-neighbors.aspx
> > [2]: http://www.sqlskills.com/BLOGS/BOBB/post/The-nearest-neighbor-optimization-in-SQL-Server-Denali.aspx
> 
>  Regards,
>  Oleg
> _____________________________________________________________
> Oleg Bartunov, Research Scientist, Head of AstroNet (www.astronet.ru),
> Sternberg Astronomical Institute, Moscow University, Russia
> Internet: oleg@sai.msu.su, http://www.sai.msu.su/~megera/
> phone: +007(495)939-16-83, +007(495)939-23-83
>