# Re: Nested interval tree encoding

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