Re: Double sorting split patch

On 15.09.2011 21:46, Alexander Korotkov wrote:
> 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)

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