Efficient Searching and Retrieval of Documents in PROSA

Vincenzo Nicosia, Giuseppe Mangioni, Vincenza Carchiolo, Michele Malgeri

Abstract

Peer-to-peer (P2P) document retrieval systems often face a trade-off between the rigid efficiency of Distributed Hash Tables (DHTs) and the high bandwidth consumption of unstructured flooding. This paper presents PROSA (P2P Resource Organisation by Social Acquaintances), a self-organizing system that routes queries based on semantic relevance and social-like relationships. By evolving links from basic acquaintances to deep semantic connections, PROSA achieves high search success rates and small-world efficiency without centralized indexing.

Introduction

In the mid-2000s, the P2P landscape was divided between structured DHTs (e.g., Chord, Pastry) and unstructured networks (e.g., Gnutella). While DHTs offer fast lookups, they struggle with complex keyword-based searching and node volatility. Unstructured systems allow flexible queries but typically rely on "flooding," which is inefficient. PROSA addresses this by modeling the network as a directed graph where links represent "social acquaintances," allowing nodes to find rare documents by leveraging local knowledge of their neighbors' expertise.

System Architecture

PROSA models network connections through a hierarchy of links that evolve over time:

  1. Acquaintance-Link (AL): A basic connection established when a node joins the network.
  2. Temporary Semantic-Link (TSL): A connection based on hints from previous successful queries.
  3. Full Semantic-Link (FSL): A strong bond established when a peer has verified the specific content hosted by another node.

When a new node (peer s) joins the network, it is initialized with a set of random parent links, as detailed in the JOIN algorithm below.

Algorithm 1: The process of a new peer joining the PROSA network and establishing initial Acquaintance-Links (AL).

As nodes interact, they perform local routing decisions. Instead of flooding, a node forwards queries to neighbors most likely to possess relevant documents. If a node has partial matches, it may initiate a limited "semantic flood" to neighbors passing a relevance threshold.

Evaluation Methodology

The system was evaluated using an event-driven Python simulator. The knowledge base consisted of 1,490 scientific articles categorized into two domains: Mathematics (740 articles) and Philosophy (750 articles). Documents were represented using a Vector Space Model (VSM) with the top 100 TF-IDF (Term Frequency-Inverse Document Frequency) weights characterizing the content.

Performance Evaluation

PROSA was compared against standard Flooding and Random Walk strategies across networks ranging from 200 to 800 nodes. Key metrics included the success rate of queries and the volume of documents retrieved.

Figure 1: Comparison of PROSA, Flooding, and Random Walk strategies regarding (a) average documents retrieved per query, (b) average documents per successful query, and (c) the percentage of answered queries.

Key Results

  • Success Rate: PROSA achieved a success rate between 84% and 92%, nearly matching the optimal but resource-intensive Flooding strategy (~94%) and significantly outperforming Random Walks.
  • Search Efficiency: PROSA maintained an average query depth of approximately 3 levels. In contrast, Flooding and Random Walks required depths of 30 to 600 levels to achieve comparable results.
  • Small-World Emergence: The network naturally evolved into a "small-world" structure characterized by high clustering (similar nodes grouping together) and short path lengths.

Conclusion

PROSA demonstrates that local routing decisions based on semantic similarity can lead to global efficiency in P2P networks. By mimicking human social learning—starting with random acquaintances and building a mental map of experts—the system excels at retrieving rare documents with minimal overhead. Future work will explore the scalability of PROSA in million-node environments and its performance across more diverse topic distributions.

Summary updated

BibTeX
@inproceedings{nicosia2006efficient,
  author = {Vincenzo Nicosia and Giuseppe Mangioni and Vincenza Carchiolo and Michele Malgeri},
  title = {{Efficient Searching and Retrieval of Documents in PROSA}},
  booktitle = {DBISP2P},
  year = {2006},
  url = {https://openreview.net/forum?id=QGHuT4AFhJ},
}
Figure