Re: k-neighbourhood search in databases

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(at)sai(dot)msu(dot)su, http://www.sai.msu.su/~megera/
phone: +007(495)939-16-83, +007(495)939-23-83