find_difference shortcut failure without walking out

Aaron Bentley aaron.bentley at utoronto.ca
Thu Dec 13 12:31:05 GMT 2007


-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Aaron Bentley wrote:
> John Arbash Meinel wrote:
>> The only algorithm I can think of off-hand, is the Greatest Distance From
>> Origin that Aaron and Robert talked about in London. Basically, every node is:
>> max(parent_distances) + 1.
> 
> It seems to me that the problem here is finding the right stop
> condition; stop too early and you incorrectly determine nodes to be
> "uncommon", stop too late and you waste resources.
> 
> So when can we stop?  When it's impossible that we can determine any
> more nodes to be common.  Since ancestry is a DAG, we know that no
> descendant of a node can also be its ancestor.  In order for a searcher
> to find that a previously-uncommon node is common, it must search from
> an ancestor of that node.

Okay, I think I swapped some terms here.  Let's try again.

So when can we stop?  When it's impossible that we can determine any
more nodes to be common.  Since ancestry is a DAG, we know that no
descendant of a node can also be its ancestor.  In order for a searcher
to find that an apparently-uncommon node is actually common, it must
search from an descendant of that node.

Therefore, when all search nodes are ancestors of all
apparently-uncommon nodes, more searching will not find any
apparently-uncommon nodes to be common.  Therefore, we can stop.

Aaron
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.6 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFHYSYJ0F+nu1YWqI0RAtrIAJ4hb7HA6hxVoDj5LuuWGEctkUAiYgCgghqo
xsxwTsg1gpB+GUyoGdxT5Po=
=zGue
-----END PGP SIGNATURE-----



More information about the bazaar mailing list