Home | Contact Us | FAQ | Search & Site Map | Link to Us
Sign In | Join | Other 45 Sites in Network
Home
Discussion Groups
Database Servers
DB2InformixIngresMS SQLOraclePervasive.SQLPostgreSQLProgressSybase
Desktop Databases
FileMakerFoxProMS AccessParadox
General
General DB TopicsDatabase Theory
Related Topics
Java Development.NET DevelopmentVB DevelopmentMore Topics ...

Database Forum / General DB Topics / DB Theory / July 2008

Tip: Looking for answers? Try searching our database.

Nested interval tree encoding

Thread view: 
Enable EMail Alerts  Start New Thread
Thread rating: 
Eric DeCosta - 03 Jul 2008 18:04 GMT
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
Eric DeCosta - 03 Jul 2008 19:38 GMT
> 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?

One possible answer, which is inelegant, but wroks is to re-compute the node
as the materialzed path is extracted and perform a check at the end and
adjust the 'tail' of the path as needed.

I'm hoping for something less brute-force...

-Eric
Tegiri Nenashi - 03 Jul 2008 22:01 GMT
> 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
[quoted text clipped - 17 lines]
>
> -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!
Tegiri Nenashi - 03 Jul 2008 22:17 GMT
>> Would using reversed continued fractions avoid this?

> 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...

Oh, as you are asking about reversed continued fractions, you are
certainly aware of the above article. To expand the answer, a version
of matrix encoding with atomic matrices of the kind:

[n  -1]
[     ]
[1   0]

correspond to reverse continued fractions. Details are in chapter 5 of
“SQL Design Patterns” book.
Eric DeCosta - 03 Jul 2008 22:45 GMT
Ah, I hadn't quite put that together, thanks.

-Eric

> On Jul 3, 10:04 am, "Eric DeCosta" <edeco...@mathworks.com> wrote:
>> Would using reversed continued fractions avoid this?

> 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...

Oh, as you are asking about reversed continued fractions, you are
certainly aware of the above article. To expand the answer, a version
of matrix encoding with atomic matrices of the kind:

[n  -1]
[     ]
[1   0]

correspond to reverse continued fractions. Details are in chapter 5 of
“SQL Design Patterns” book.
Eric DeCosta - 03 Jul 2008 22:37 GMT
In my particular exploration of this topic, I do, indeed have all four
elements of a 2x2 matrix stored -- and the right column is the continued
fraction of the node's parent; so I don't think the properties of adjacency
list are particular to Farey fractions.

From what reading I have done, Farey fractions also suffer from 'first
child' problems, but perhaps the articles you site will elucidate the issue
a bit more.  Thanks for the pointers.

-Eric

>> I'e been tring to develop a workable implementation of nested interval
>> tree
[quoted text clipped - 38 lines]
> with the child left column -- a bonus referential integrity constraint
> that we have in adjacency list encoding!
Tegiri Nenashi - 03 Jul 2008 23:31 GMT
> In my particular exploration of this topic, I do, indeed have all four
> elements of a 2x2 matrix stored

Then, applying the extended Euclidean algorithm is unambiguous, right?
The sigmod paper p.4 illustrates how to expand the matrix by adding
more columns. The algorithm stops as soon as we add column [0,1].

> -- and the right column is the continued
> fraction of the node's parent; so I don't think the properties of adjacency
> list are particular to Farey fractions.

I'm not sure I understand your comment. Sure the left column [3,4] of
the child
[3 5]
[4 7]
refers to the right column of the parent
[2 3]
[3 4]
In this sense it is similar to adjacency list. The difference, of
course, is that in matrix encoding we have a very strict policy what
values are admitted, and in adjacency list you can label tree nodes by
anything.
Tegiri Nenashi - 03 Jul 2008 23:58 GMT
> [3 5]
> [4 7]

To expand it a little more, considering the above matrix what fraction
3/4 or 5/7 we choose as tree encoding? I suggest that thinking of tree
node encoded by a single fraction is a wrong idea. The node is encoded
by the interval [3/4,5/7). But then we have this inconvenience of the
intervals changing orientation every time we go one level up in the
tree. Changing orientation is not really a show stopper, but one have
to be careful when writing nesting interval condition in SQL queries.

The crux of the problem is the alternating matrix determinant. Dan's
solution is to interleave materialized path with 1's so that

3.4.5

becomes something like

3.1.4.1.5.1

Dan's approach is essentially matrix encoding with atomic matrices of
the kind

[n + 1  n]
[         ]
[ 1     1]

Each atomic matrix has determinant equal to one, therefore we see that
even if we multiply them, the determinant are not alternating, and
nested interval orientation does not change when we ascend to the next
tree level. Each Dan’s atomic matrix is a product of the familiar
atomic matrix

[n 1]
[ ]
[1 1]

with an auxiliary matrix

[1 1]
[ ]
[1 0]

This is why Dan’s continued fractions contain interleaving sequences
of 1s.

An alternative to Dan's approach is suggested in chapter 5 of "SQL
design patterns" book. The atomic matrices of the kind

[n + 1  -1]
[         ]
[ 1     0]

also always have determinant 1. One more encoding with this property
is hinted in the book exercises:

[n + 1  i]
[         ]
[ i     0]

This was perhaps an attempt to keep the determinant property, and also
be able to organize matrices into the number wall which was lost for
the

[n + 1  -1]
[         ]
[ 1     0]

encoding. (Not that there is a compelling practical reason to insist
on number wall property).
 
Sign In
Join
My Latest Posts
My Monitored Threads
My Blog
My Photo Gallery
My Profile
My Homepage

Start New Thread
Enable EMail Alerts
Rate this Thread



©2008 Advenet LLC   Privacy Policy - Terms of Use
This website includes both content owned or controlled by Advenet as well as content owned or controlled by third parties.