[Date Prev][Date Next][Thread Prev][Thread Next][Author Index][Date Index][Thread Index]

*To*: <ravi>*Subject*: Region splay*From*: Eric Dean Tribble <tribble>*Date*: Thu, 1 Feb 90 12:29:16 PST*Cc*: <dean>, <markm>, <xtech>*In-reply-to*: <Ravi>,34 PST <9002011911.AA00592@xanadu>

MarkM observed when I first started thinking about a region splay operation that we should just get a simply splay operation working because once the structure existed and we all had time to bounce the spaly stuff around (bby February, say), it would all be much easier to think about. Congratulations, you're right on time! - isolates the region in its own subtree and brings it to the top - groups the tree according to the kind of regions it gets as requests (hence does not require any external grouping heuristic) - does extra search only if the requests (hence grouping) don't correspond well to the simple regions in the space - works fine in the presence of overlapping subtree regions, but it may do some extra searching These are exactly the properties I started with for a region splay operation, and they are sufficient to be wonderful. While discussing my algorithm sketch with Markm, we noticed that enfilades needed grouping heuristics and overlap in order to maintain balance. With splay trees, we can probably transform the tree during splay operations from one non-overlapping tree to another. Your approach using tables of transformation rules should easily extend to figure out if this makes sense. non-overlapping issues only make sense for simple regions, however. More on this later. It's going to be fun proving that any of these algorithms are still amortized log-bounded. It might even be easy.... Return 0, 1, or 2 according to the number of my children that are in the region. If 1, then the left child is in the region, and the right child outside." This by itself would simplify the algorithm. 0 2 (A B*) -> (B* A) 1 Cute! Virtual and partial loaves need to replace themselves with an actual subtree in which the leaves are all in or all out of the region, and return the result from splaying it. It's sufficiently complicated that I don't see any need to implement the algorithm right away, but it's nice to know it'll be there when we need it. How much different is it from the algorithm that you already coded? The algorithm looks correct, and your approach to the algorithm certainly is a clarifying way to think about it and understand it.. After FM I'll wrap it around the hard cases. If it still looks correct, I'll add this algorithm when I next revamp the ent (to get rid of SpatialBehaviors). P.S. Dean: the algorithm you posted will work fine for the multi-dimensional case, but not for a region splay of, say, every fifth element, where the grouping algorithm has no way to know how to keep things in the region together across distinction splays. For arbitrary regions, you really need to do the splay all at once. The first sketch of the algorithm I posted used the count of distinctions only as a count. Further discussion with MarkM immediately eliminated the use of distinctions. It used the full region for grouping, so would result in similar tree structures (assuming it worked!). Your algorithm is abstractly similar, but much simpler and clearer. Great Work! dean PS: Ravi: where would you like to go for dinner? :-)

- Prev by Date:
**Region splay** - Next by Date:
**Re: Berts&Orgls** - Previous by thread:
**Region splay** - Next by thread:
**Weekly Planning Meeting, 1/30** - Index(es):