WWW2007 Poster Details
Poster Title:
SCAN: A Small-World Structured P2P Overlay for Multi-Dimensional Queries
  • Xiaoping Sun (Institute of Computing Technology, Graduate School of Chinese Academy of Sciences)
This paper presents a structured P2P overlay SCAN that augments CAN overlay with long links based on Kleinberg's small-world model in a d-dimensional Cartesian space. The construction of long links does not require estimate of network size. Queries in multi-dimensional data space can achieve O(2log(dn^1/d)) hops by equipping each node with O(log(dn^1/d)) long links and O(d) short links.
PDF version