Обсуждение: k-neighbourhood search in databases

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

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
cando 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

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
databasecan 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

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

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

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

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

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