# Re: Nested interval tree encoding

From: Eric DeCosta <edecosta_at_mathworks.com>
Date: Thu, 3 Jul 2008 17:37:56 -0400
Message-ID: <g4jgrk\$95d\$1_at_fred.mathworks.com>

In my particular exploration of this topic, I do, indeed have all four elements of a 2x2 matrix stored -- and the right column is the continued fraction of the node's parent; so I don't think the properties of adjacency list are particular to Farey fractions.

From what reading I have done, Farey fractions also suffer from 'first child' problems, but perhaps the articles you site will elucidate the issue a bit more. Thanks for the pointers.

-Eric

"Tegiri Nenashi" <TegiriNenashi_at_gmail.com> wrote in message news:1f8986cd-04ca-4b53-b6f2-d3f25658f474_at_w1g2000prd.googlegroups.com...
> On Jul 3, 10:04 am, "Eric DeCosta" <edeco..._at_mathworks.com> wrote:
>> I'e been tring to develop a workable implementation of nested interval
>> tree
>> encoding using continued
>> fractions:http://arxiv.org/ftp/cs/papers/0402/0402051.pdf
>>
>> However, I'm running into a snag when I try to decode the materialzed
>> path
>> of certain nodes using the Euclidean algorithm. The first child node of
>> any
>> parent does not decode properly; for instance: 3.12.5.21.1 which is
>> correctly encoded as the continued fraction of 4173/1354 is decoded as
>> 3.12.5.22:
>>
>> 4173 = 1354 * 3 + 111
>> 1354 = 111 * 12 + 22
>> 111 = 22 * 5 + 1
>> 22 = 1 * 22 + 0
>>
>> Other nodes like 3.12.5.21, 3.12.5.22, and 3.12.5.21.2 are correctly
>> decoded; so this looking like a special case involving the first child
>> node.
>>
>> Is there any way to detect and handle this without looking-up the parent
>> node? Would using reversed continued fractions avoid this?
>>
>> -Eric
>
> There are several ways around this snag.
>
> Dan Hazel's enhanced version of the continued fraction encoding
> http://arxiv.org/abs/0806.3115
>
> Then, there is matrix encoding which is essentially the same as
> continued fractions but IMO provide more insight:
> http://www.sigmod.org/sigmod/record/issues/0506/p47-article-tropashko.pdf
> Farey fraction consists of the two integers which correspond one
> column of the matrix. Knowing one column of the matrix is not enough,
> but adding just a tiny bit extra -- the sign of the determinant would
> suffice. But then storage is cheap, why not have all the four matrix
> values? The added advantage is that the parent right column coincides
> with the child left column -- a bonus referential integrity constraint
> that we have in adjacency list encoding!
Received on Thu Jul 03 2008 - 23:37:56 CEST

Original text of this message