Questions about nested intervals. Help me please!!!

Thread view:

Enable EMail Alerts

Start New Thread

Thread rating:

ampharos - 18 Jul 2005 21:10 GMT

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?

Thanks for the attention

Reply to this Message

Vadim Tropashko - 18 Jul 2005 21:48 GMT

> I'm an italian student of computer science and I'm trying to do an
> implementation of nested intervals with continued fractions.
[quoted text clipped - 7 lines]
> 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.

Reply to this Message

ampharos - 19 Jul 2005 21:10 GMT

Thanks for the answers,
in particular way, using farey encoding, how can I relocating subtrees
in nested interval model?

:) excuse me for my very bed english :)

Vadim Tropashko ha scritto:

> > I'm an italian student of computer science and I'm trying to do an
> > implementation of nested intervals with continued fractions.
[quoted text clipped - 35 lines]
> 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.

Reply to this Message

Vadim Tropashko - 20 Jul 2005 00:01 GMT

> Thanks for the answers,
> in particular way, using farey encoding, how can I relocating subtrees
> in nested interval model?
> Thanks for the answers,
> in particular way, using farey encoding, how can I relocating subtrees
> in nested interval model?

The key idea for answering your question is to represent Farey encoding
with matrices. Why matrices are required? Because matrix multiplication
mimics materialized paths concatenation!

Disclamer. During the discussion below I'll use materialized path as an
easy reference. This is only to guide the intuition. The formal answer
doesn't refer to materialized path at all.

Consider node 2.2.3, for example. Farey encoding for this node is found
by presenting materialized path as a continued fraction

1/(2+1/(2+1/(3))) = 7/17
1/(2+1/(2+1/(3+1))) = 9/22

Since 7/17>9/22, then our Farey Interval is (9/22,7/17). This is the
node that we want to move to another position, say 1.4. Farey encoding
for 1.4 is calculated similarly (4/5,5/6).

Take any descendant of (9/22,7/17), say 2.2.3.4.1=(37/90,67/163).

In short:
(9/22,7/17) -> (4/5,5/6)
(37/90,67/163) -> ???

Once again, we have to convert Farey fractions into matrix form.
Getting them into Moebius encoding is intermediatory step:

(9/22, 7/17) = (2x+7)/(5x+17), where 0<x<1
(4/5, 5/6) = (1x+4)/(1x+5), where 0<x<1
(37/90,67/163) = (30x+37)/(73x+90), where 0<x<1

Therefore, in matrix terms

[[2,7],[5,17]] -> [[1,4],[1,5]]
[[30,37],[73,90]] -> ???

Remember, we (rather arbitrarily) selected node [[30,37],[73,90]] as a
descendant of [[2,7],[5,17]]. This implies that there is a matrix
[[a,b],[c,d]] that satisfies the equation

[[2,7],[5,17]]*[[a,b],[c,d]]=[[30,37],[73,90]]

Here I take a little jump, assuming that finding a,b,c,d is easy for
anybody with rudimentary linear algebra skills. (Previous version of
the paper http://arxiv.org/pdf/cs.DB/0402051v1 had little bit more
details how to find a,b,c,d).

[[a,b],[c,d]]=[[1,1],[4,5]]

As you need a generic solution, you would have to write down the
solution explicitly as formulas for a,b,c,d in terms of the components
of the two known matrices.

The final step is multiplying

[[1,4],[1,5]]*[[a,b],[c,d]]=
[[1,4],[1,5]]*[[1,1],[4,5]]=
[[17,21],[21,26]]

which is the answer. (Why the matrix is symmetric? The path 1.4.4.1 is
symmetric!)

We have to get it back to Farey encoding
[[17,21],[21,26]] ---> (17x+21)/(21x+26), where 0<x<1
(17x+21)/(21x+26) ---> (17/21,38/47)

Reply to this Message

Mikito Harakiri - 20 Jul 2005 00:12 GMT

> Remember, we (rather arbitrarily) selected node [[30,37],[73,90]] as a
> ... there is a matrix that satisfies the equation
[quoted text clipped - 3 lines]
> Here I take a little jump, assuming that finding a,b,c,d is easy for
> anybody with rudimentary linear algebra skills.

This is fairly easy. What is the inverse of [[2,7],[5,17]]? For 2x2
matrices the inverse calculation is trivial:

[[x11,x12],[x21,x22]]^(-1) =
det([[x11,x12],[x21,x22]]) * [[x22,-x12],[-x21,x11]]

which gives in this case

[[2,7],[5,17]]^(-1) = [[-17,7],[5,-2]]

Left mutiply

[[2,7],[5,17]]*[[a,b],[c,d]]=[[30,37],[73,90]]

both sides by [[-17,7],[5,-2]]

[[a,b],[c,d]]=[[-17,7],[5,-2]]*[[30,37],[73,90]]=[[1,1],[4,5]]

Reply to this Message