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