<meta http-equiv="content-type" content="text/html; charset=utf-8"><div>It's O(N*log(N)), or more particular O(M*N*log(N)), where M - number of dimensions.</div><meta http-equiv="content-type" content="text/html; charset=utf-8"><div>

My experimens show that difference in CPU usage with linear algorithm is insignificant.</div><div><br></div>------<br>With best regards,<br>Alexander Korotkov. <div><br><div class="gmail_quote">On Wed, Oct 12, 2011 at 10:59 PM, Paul Ramsey <span dir="ltr"><<a href="mailto:pramsey@opengeo.org">pramsey@opengeo.org</a>></span> wrote:<br>

<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">Is the algorithm still O(N) or is it O(N^2) ala Guttman?<br>
P.<br>
<br>
On Wed, Oct 12, 2011 at 11:58 AM, Alexander Korotkov<br>
<div><div></div><div class="h5"><<a href="mailto:aekorotkov@gmail.com">aekorotkov@gmail.com</a>> wrote:<br>
> "A new double sorting-based node splitting algorithm for R-tree", A. Korotkov<br>
> <a href="http://syrcose.ispras.ru/2011/files/SYRCoSE2011_Proceedings.pdf#page=36" target="_blank">http://syrcose.ispras.ru/2011/files/SYRCoSE2011_Proceedings.pdf#page=36</a><br>
> I believe it's applicable to not very high dimensions (3 or 4). On 5 and<br>
> more dimensions guttmann quadratic algorithm could become more effective<br>
> than my.<br>
> ------<br>
> With best regards,<br>
> Alexander Korotkov.<br>
> On Wed, Oct 12, 2011 at 10:49 PM, Paul Ramsey <<a href="mailto:pramsey@opengeo.org">pramsey@opengeo.org</a>> wrote:<br>
>><br>
>> And, in general terms, do you think this approach would be applicable<br>
>> in higher dimensions?<br>
>> P<br>
>><br>
>> On Wed, Oct 12, 2011 at 11:49 AM, Paul Ramsey <<a href="mailto:pramsey@opengeo.org">pramsey@opengeo.org</a>> wrote:<br>
>> > Thanks for this, could you give me a reference to your paper too?<br>
>> > P.<br>
>> ><br>
>> > On Wed, Oct 12, 2011 at 10:52 AM, Alexander Korotkov<br>
>> > <<a href="mailto:aekorotkov@gmail.com">aekorotkov@gmail.com</a>> wrote:<br>
>> >> Hi!<br>
>> >> Heikki Linnakangas recently commit my patch with new node splitting<br>
>> >> algorithm for GiST to PostgreSQL master branch:<br>
>> >><br>
>> >> <a href="http://git.postgresql.org/gitweb/?p=postgresql.git;a=commitdiff;h=7f3bd86843e5aad84585a57d3f6b80db3c609916" target="_blank">http://git.postgresql.org/gitweb/?p=postgresql.git;a=commitdiff;h=7f3bd86843e5aad84585a57d3f6b80db3c609916</a><br>


>> >> Since it can significantly accelerate index search, you might be<br>
>> >> interested<br>
>> >> to apply same changes to PostGIS.<br>
>> >> Discussion threads are here:<br>
>> >> <a href="http://archives.postgresql.org/pgsql-hackers/2011-10/msg00158.php" target="_blank">http://archives.postgresql.org/pgsql-hackers/2011-10/msg00158.php</a><br>
>> >> <a href="http://archives.postgresql.org/pgsql-hackers/2011-09/msg00576.php" target="_blank">http://archives.postgresql.org/pgsql-hackers/2011-09/msg00576.php</a><br>
>> >> ------<br>
>> >> With best regards,<br>
>> >> Alexander Korotkov.<br>
>> >> _______________________________________________<br>
>> >> postgis-devel mailing list<br>
>> >> <a href="mailto:postgis-devel@postgis.refractions.net">postgis-devel@postgis.refractions.net</a><br>
>> >> <a href="http://postgis.refractions.net/mailman/listinfo/postgis-devel" target="_blank">http://postgis.refractions.net/mailman/listinfo/postgis-devel</a><br>
>> >><br>
>> >><br>
>> ><br>
>> _______________________________________________<br>
>> postgis-devel mailing list<br>
>> <a href="mailto:postgis-devel@postgis.refractions.net">postgis-devel@postgis.refractions.net</a><br>
>> <a href="http://postgis.refractions.net/mailman/listinfo/postgis-devel" target="_blank">http://postgis.refractions.net/mailman/listinfo/postgis-devel</a><br>
><br>
><br>
> _______________________________________________<br>
> postgis-devel mailing list<br>
> <a href="mailto:postgis-devel@postgis.refractions.net">postgis-devel@postgis.refractions.net</a><br>
> <a href="http://postgis.refractions.net/mailman/listinfo/postgis-devel" target="_blank">http://postgis.refractions.net/mailman/listinfo/postgis-devel</a><br>
><br>
><br>
_______________________________________________<br>
postgis-devel mailing list<br>
<a href="mailto:postgis-devel@postgis.refractions.net">postgis-devel@postgis.refractions.net</a><br>
<a href="http://postgis.refractions.net/mailman/listinfo/postgis-devel" target="_blank">http://postgis.refractions.net/mailman/listinfo/postgis-devel</a><br>
</div></div></blockquote></div><br></div>