# Nested interval tree encoding

From: Eric DeCosta <edecosta_at_mathworks.com>

Date: Thu, 3 Jul 2008 13:04:17 -0400

Message-ID: <g4j0qh$k0e$1_at_fred.mathworks.com>

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

Date: Thu, 3 Jul 2008 13:04:17 -0400

Message-ID: <g4j0qh$k0e$1_at_fred.mathworks.com>

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

Is there any way to detect and handle this without looking-up the parent node? Would using reversed continued fractions avoid this?

-Eric Received on Thu Jul 03 2008 - 19:04:17 CEST