[postgis-devel] New node splitting algorithm for GiST

Paul Ramsey pramsey at opengeo.org
Wed Oct 12 12:07:46 PDT 2011


NM, I actually read the paper :)
P.

On Wed, Oct 12, 2011 at 11:59 AM, Paul Ramsey <pramsey at opengeo.org> wrote:
> Is the algorithm still O(N) or is it O(N^2) ala Guttman?
> P.
>
> On Wed, Oct 12, 2011 at 11:58 AM, Alexander Korotkov
> <aekorotkov at gmail.com> wrote:
>> "A new double sorting-based node splitting algorithm for R-tree", A. Korotkov
>> http://syrcose.ispras.ru/2011/files/SYRCoSE2011_Proceedings.pdf#page=36
>> I believe it's applicable to not very high dimensions (3 or 4). On 5 and
>> more dimensions guttmann quadratic algorithm could become more effective
>> than my.
>> ------
>> With best regards,
>> Alexander Korotkov.
>> On Wed, Oct 12, 2011 at 10:49 PM, Paul Ramsey <pramsey at opengeo.org> wrote:
>>>
>>> And, in general terms, do you think this approach would be applicable
>>> in higher dimensions?
>>> P
>>>
>>> On Wed, Oct 12, 2011 at 11:49 AM, Paul Ramsey <pramsey at opengeo.org> wrote:
>>> > Thanks for this, could you give me a reference to your paper too?
>>> > P.
>>> >
>>> > On Wed, Oct 12, 2011 at 10:52 AM, Alexander Korotkov
>>> > <aekorotkov at gmail.com> wrote:
>>> >> Hi!
>>> >> Heikki Linnakangas recently commit my patch with new node splitting
>>> >> algorithm for GiST to PostgreSQL master branch:
>>> >>
>>> >> http://git.postgresql.org/gitweb/?p=postgresql.git;a=commitdiff;h=7f3bd86843e5aad84585a57d3f6b80db3c609916
>>> >> Since it can significantly accelerate index search, you might be
>>> >> interested
>>> >> to apply same changes to PostGIS.
>>> >> Discussion threads are here:
>>> >> http://archives.postgresql.org/pgsql-hackers/2011-10/msg00158.php
>>> >> http://archives.postgresql.org/pgsql-hackers/2011-09/msg00576.php
>>> >> ------
>>> >> With best regards,
>>> >> Alexander Korotkov.
>>> >> _______________________________________________
>>> >> postgis-devel mailing list
>>> >> postgis-devel at postgis.refractions.net
>>> >> http://postgis.refractions.net/mailman/listinfo/postgis-devel
>>> >>
>>> >>
>>> >
>>> _______________________________________________
>>> postgis-devel mailing list
>>> postgis-devel at postgis.refractions.net
>>> http://postgis.refractions.net/mailman/listinfo/postgis-devel
>>
>>
>> _______________________________________________
>> postgis-devel mailing list
>> postgis-devel at postgis.refractions.net
>> http://postgis.refractions.net/mailman/listinfo/postgis-devel
>>
>>
>



More information about the postgis-devel mailing list