Re: Nested interval tree encoding
Date: Thu, 3 Jul 2008 17:37:56 -0400
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.
"Tegiri Nenashi" <TegiriNenashi_at_gmail.com> wrote in message
> 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
>> encoding using continued
>> However, I'm running into a snag when I try to decode the materialzed
>> of certain nodes using the Euclidean algorithm. The first child node of
>> parent does not decode properly; for instance: 188.8.131.52.1 which is
>> correctly encoded as the continued fraction of 4173/1354 is decoded as
>> 4173 = 1354 * 3 + 111
>> 1354 = 111 * 12 + 22
>> 111 = 22 * 5 + 1
>> 22 = 1 * 22 + 0
>> Other nodes like 184.108.40.206, 220.127.116.11, and 18.104.22.168.2 are correctly
>> decoded; so this looking like a special case involving the first child
>> Is there any way to detect and handle this without looking-up the parent
>> node? Would using reversed continued fractions avoid this?
> There are several ways around this snag.
> Dan Hazel's enhanced version of the continued fraction encoding
> Then, there is matrix encoding which is essentially the same as
> continued fractions but IMO provide more insight:
> 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