On 15.09.2011 21:46, Alexander Korotkov wrote:
On Thu, Sep 15, 2011 at 7:27 PM, Heikki Linnakangas<
heikki.linnakan...@enterprisedb.com> wrote:
I've looked at the patch, and took a brief look at the paper - but I still
don't understand the algorithm. I just can't get my head around the concepts
of split pairs and left/right groups. Can you explain that in layman's
terms? Perhaps an example would help?
In short algorithm works as following:
1) Each box can be projected to the axis as an interval. Box (x1,y1)-(x2,y2)
are projected to X axis as (x1,x2) interval and to the Y axis as (y1,y2)
interval. At the first step we search for splits of those intervals and
select the best one.
2) At the second step produced split are converting into terms of boxes
and ambiguities are solving.
Let's see a little deeper how intervals split search are performed by
considering an example. We've intervals (0,1), (1,3), (2,3), (2,4). We
assume intervals of the groups to be (0,a), (b,4). So, "a" can be some upper
bound of interval: {1,3,4}, and "b" can be some lower bound of inteval:
{0,1,2}.
We consider following splits: each "a" with greatest possible "b"
(0,1), (1,4)
(0,3), (2,4)
(0,4), (2,4)
and each "b" with least possible "a". In this example splits will be:
(0,1), (0,4)
(0,1), (1,4)
(0,3), (2,4)
By removing the duplicates we've following splits:
(0,1), (0,4)
(0,1), (1,4)
(0,3), (2,4)
(0,4), (2,4)
Ok, thanks, I understand that now.
Proposed algorithm finds following splits by single pass on two arrays: one
sorted by lower bound of interval and another sorted by upper bound of
interval.
That looks awfully complicated. I don't understand how that works. I
wonder if two passes would be simpler?
--
Heikki Linnakangas
EnterpriseDB http://www.enterprisedb.com
--
Sent via pgsql-hackers mailing list (pgsql-hackers@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-hackers
