Re: Nested interval tree encoding

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:01:48 CEST