[Date Prev][Date Next][Thread Prev][Thread Next][Author Index][Date Index][Thread Index]
partial orgl implementation
- To: <us>
- Subject: partial orgl implementation
- From: Eric Dean Tribble <tribble>
- Date: Mon, 18 Sep 89 02:39:00 PDT
For those following the story, I think the right first implementation
for partial orgls is to walk up the ent, rebalancing to accommodate
the newly informed data. The original algorithm MarkM and I sketched
out actually ended up rebalancing one tree in place while preserving
all the previous pointers into existing subTrees. I think the routine
for rebalancing one tree in place can just be applied to all the
existing parents of a partial crum. The symmetric operation should be
much easier to think about and reduce to code. (So far I'm running on
intuition: I can't keep the whole algorithm in my head at once! :-).
Tomorrow I will verify that canopies are maitained by the algorithm,
and then start coding).
A consequence of rebalancing in place is that the data-inform
operation has a complexity based on the number of derived partial
orgls. Since the complexity is based on rebalancing, it's probably
what MarkM calls amortized-log-bounded.
Another consequence is that original and derived partial orgls are
indistinguishable. Even if we avoid allowing informs on derived
partial orgls in the higher level semantics, it lets us move the
destination of a sensor from its original partial orgl (hat can be
filled with all sorts of junk) to a copy of the still-partial part of
the original partial orgl. That way the existence of the sensor won't
require the original orgl to exist.
dean