Top of Menu Home CFP Program Committees Key Dates Location Hotel Registration Students Sponsors Media Submission Tutorials Workshops Travel Info Proceedings

Poster Papers

Track: Search

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


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