Popularity-Biased Random Walks for Peer-to-Peer Search Under the Square-Root Principle

The square-root principle is known to achieve low search time for peer-to-peer search techniques that do not utilize query routing indices (e.g., query flooding or random walk searches). Under this principle, each object is probed with probability proportional to the square root of its query popularity. Existing search methods realize the square-root principle by using either object replication or topology reconstruction, which may not be desirable for those applications with large, dynamic datasets and limited network bandwidth. The authors propose a new approach that uses popularity biased random walks to achieve the squareroot principle.