Poster Title:

SCAN: A Small-World Structured P2P Overlay for Multi-Dimensional Queries

Authors:

• Xiaoping Sun (Institute of Computing Technology, Graduate School of Chinese Academy of Sciences)

Abstract:

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.