Loading ...
Sorry, an error occurred while loading the content.

5992Re: [decentralization] random walk searches

Expand Messages
  • Johannes Ernst
    Jul 7, 2002
      Thanks for the clarifications.

      At 19:43 -0400 2002/07/07, Lucas Gonze wrote:


      > > Otherwise, it would be interesting if someone found an effective way
      >> of implementing an A* -type algorithm in a p2p system. Anyone ever
      >> done that?
      >A*, Johannes?

      Goes back to AI in the 70's as far as I know (but then, I'm just an
      EE so I might not know). I read about it first in Winston's
      Artificial Intelligence, MIT 1979. (I quoted it in my PhD thesis but
      don't actually own the book so this is from -- weak -- memory)

      It's basically a search algorithm that selects the next node based on
      an estimate of the distance between the current node and where the
      result may be. As far as I recall, it is proven to be optimal (with
      respect to the number of nodes traversed) for "good-enough"
      estimation functions. Depending on what the estimate says, it turns
      out to be breadth or depth first at the extremes. Surprisingly, "good
      enough" does not need to be particularly good. I think
      underestimation of distance was always okay, overestimation was bad,
      but I would think that one should be able to distribute data over a
      p2p network in a way that a corresponding "appropriate" estimation
      function could be constructed?!?
    • Show all 17 messages in this topic