From: ampharos <stefanobruno79_at_gmail.com>
Date: 19 Jul 2005 13:10:10 -0700

in particular way, using farey encoding, how can I relocating subtrees in nested interval model?
:) excuse me for my very bed english :)

> ampharos wrote:
> > I'm an italian student of computer science and I'm trying to do an
> > implementation of nested intervals with continued fractions.
> > >From how much I have understood continued fractions are only a way in
> > order to pass from an encoding (example Farey encoding) to materialized
> > path.
> > My objective is that one to implement hierarchical structures in the
> > more efficient way and and to allow operation of insert,delete and move
> > of nodes.
> > Which is the best encoding applicable to nested intervals? Already
> > exists an implementation of this encoding?
> > With Farey encoding how I can use continued fractions?
>
> Could you please be more specific? For example, suppose that I have
> each node encoded as a matrix of 4 numbers
>
> [
> [a11,a12],
> [a21,a22]
> ]
>
> and want to calculate the beginning and the end points of the interval.
>
> Or given the matrix above, how to find out the materialized path? Or,
> given the matrix above, how to find it's parent, next sibling, and the
> first child? Or given the two matrices A and B, is B the descendant of
> A?
>
> The
> http://arxiv.org/pdf/cs.DB/0402051
> paper tells how answers all these questions, but you may ask to clarify
> any ideas from there. Just be more specific.
>
>
> Which encoding is the best?
> http://www.sigmod.org/sigmod/record/issues/0506/p47-article-tropashko.pdf
> demonstrates that dyadic fractions, and farey/continued fractions are
> the two most natural choices.
>
> Farey/continued fractions encoding is more ecomomical: it grows as
> 1.61^n (where 1.61 is the golden mean) versus 2^n for dyadic fractions.
Received on Tue Jul 19 2005 - 22:10:10 CEST

Original text of this message