Title: Search in Structured Peer-to-Peer Architectures with Dot-Products

Authors:Hung-Chang Hsiao and Chung-Ta King.

Date: January 1, 2003

Abstract

Peer-to-peer overlays widely received attention since these overlays can be rapidly deployed services and applications over end-systems without sophisticated network support in the large-scale Internet. End-systems joining an overlay can provide plentiful resources for computational tasks and information. To search items fulfilling the designated characterization from a large-scale overlay without the centralized help thus becomes an issue. In this paper, we propose a design called Meteorograph atop structured peer-to-peer overlays to support partial-match search. Meteorograph is based on the vector space model, where each item stored is characterized by a set of keywords and thus can be represented as a vector. Two items are similar if they share the similar sets of keywords. This thus leads to the angle between their vector representations become small. Based on such a concept, Meteorograph calculates each item’s location in the overlay and controls its published location. To retrieve a set of similar items, the request can be simply forwarded to those nearby nodes responsible for storing the requested items. The simulation results present that searching a set (in size k) of similar items (each is in size s) takes O(logN+(ks)/c) hops and messages.