I could be wrong, but I think this is equivalent or similar to a scheme that was proposed a while ago (perhaps by me - I can't recall).
This stuck with the current DBR system, but when today's edition didn't exist it would try yesterdays, then 4 days ago, then 8 days ago, then 16, exponentially searching backwards. When a page is found it exponentially searches forwards in a similar manner, then backwards, forwards, etc etc (sorry not a clear explanation, I will leave it as an exercise for the reader to fill in the details). In common with your suggestion, this should find the most recent edition in logarithmic time. Ian. On Mon, Dec 03, 2001 at 07:05:16PM -0500, Scott Young wrote: > DBR's can be modified to allow freesite authors to update whenever they want. > I will show this idea by example, so lets say someone inserts a DBR site at > the following ascending times (in binary, and in an arbitrary time format): > > 1. 00110100 > 2. 00110101 > 3. 00111100 > 4. 00111111 > 5. 01001010 > 6. 01010100 > > The binary tree equivalents would be inserted as > > 1. 0 > 2. 00 > 3. 001 > 4. 0011 > 5. 01 > 6. 010 > > Basically, the next insert chopps off all of the ending uncommon bits with > the last tree and then adds the most significant one that it does not share > with the previous tree. If the current time is > 01010010 > then the algorithm will search for > 01010010 > 0101001 > 010100 > 01010 > 0101 > 010 > 01 > 0 > in order until it recieves one (or it could do several at once). After that, > it tries to traverse down the tree to see if there are any newer versions. > This may seem like a lot of overhead, but there are several optimizations > that can be made with it. > > Scott Yourg > > _______________________________________________ > Devl mailing list > Devl at freenetproject.org > http://lists.freenetproject.org/mailman/listinfo/devl -- Ian Clarke ian at freenetproject.org Founder & Coordinator, The Freenet Project http://freenetproject.org/ Chief Technology Officer, Uprizer Inc. http://www.uprizer.com/ -------------- next part -------------- A non-text attachment was scrubbed... Name: not available Type: application/pgp-signature Size: 232 bytes Desc: not available URL: <https://emu.freenetproject.org/pipermail/devl/attachments/20011203/6585866b/attachment.pgp>
