Data Indexing and Querying in DHT Peer-to-Peer Networks
Guillaume Urvoy-Keller · 2003
Peer-to-peer DHT systems, such as Chord [8], CAN [5], Pastry [6], or Tapestry [11], make it simple to discover specific data when their complete identifiers—or keys—are known in advance. In practice, however, users looking up resources stored in peer-to-peer systems often have only partial information for identifying these resources and tend to submit broad queries. In this paper, we describe techniques for indexing data stored in peer-to-peer networks, and discovering the resources that match a given user query. Our system creates multiple indexes, organized hierarchically, which permit users to access data in many different ways. Indexes are distributed across the nodes of the network and contain key-to-key (or query-to-query) mappings. Given a broad query, a user can look up the more specific queries that match the original query; the DHT can be recursively queried until the user finds the desired data items. The data itself is stored on only one (or few) of the nodes. Our indexing techniques have several interesting properties, such as good scalability, loose coupling between data and indexes, decentralized architecture, and reasonably-small space requirements. Look-up times depend on the “precision” of the initial query: broad queries incur higher lookup times than specific queries. Note that we do not aim at answering complex database-like queries, but rather at providing practical techniques for searching data using more advanced tools than exact or simple keyword lookups.