Re: Double sorting split patch

On Thu, Sep 15, 2011 at 7:27 PM, Heikki Linnakangas <
heikki(dot)linnakangas(at)enterprisedb(dot)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)
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.

------
With best regards,
Alexander Korotkov.