On Nov 17, 2006 13:48 -0800, Terry Heidelberg wrote: > Yang Liu <[EMAIL PROTECTED]> wrote: > >I think I see the problem. Such an query would not return intervals that > >are completely contained within [A,B] (i.e. all [C,D] where A<C<D<B). > > Yang Liu wrote: > >Have you guys looked at relational interval trees? > >http://www.dbs.informatik.uni-muenchen.de/Forschung/CAD/presentations/RI-Tree.pdf > >
I stopped reading the paper after the title reported "Patent pending"... Zach pointed me at "interval trees" on Wikipedia which seem like the right thing. They are like interval skip lists, but with a clever twist to handle the case where intervals wholly overlap as Yang Liu suggests. It might make sense to keep some special values out of the tree, like [0,EOF] locks, since we know they will match every interval. Cheers, Andreas -- Andreas Dilger Principal Software Engineer Cluster File Systems, Inc. _______________________________________________ Lustre-devel mailing list [email protected] https://mail.clusterfs.com/mailman/listinfo/lustre-devel
