Re: Questions about nested intervals. Help me please!!!

From: Vadim Tropashko <vadimtro_invalid_at_yahoo.com>
Date: 18 Jul 2005 13:48:48 -0700
Message-ID: <1121719727.995993.64560_at_g14g2000cwa.googlegroups.com>


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 Mon Jul 18 2005 - 22:48:48 CEST

Original text of this message