Design space for distributed search (DS)²: a system designers' guide

Abstract

Important research efforts are conducted in the area of search, lookup, and routing, and are even increasing in light of promises and challenges of peer-to-peer (P2P) systems or the semantic web. To organize these areas of concern, this paper proposes an exhaustive two-dimensional design space that structures and classifies current and facilitates future research. In the functional dimension, it identifies a series of mappings and integrated approaches like keyword lookup or semantic routing. In the structural dimension, design options for each mapping include computational approaches, central or completely replicated tables, classic or symmetric hierarchies, ordered spaces, as well as random structures and topologies. An evaluation of these design options serves as a guideline for system designers and leads to the design of a novel peer-to-peer based keyword routing scheme. It also leads to general implications and recommendations for P2P search design.