Efficient Peer-to-Peer Keyword SearchUsing Adaptive Space Partition
Po-Hung Chen · 2004
Locating the node that stores a particular data item is a fundamental problem in peer-topeer systems and is traditionally formulated as the construction of a distributed hash table (DHT). Typical DHTs support only a simple map from keys to values, but not keyword search. To support keyword search on a DHT, some distributed inverted index is needed. The challenge is how to evenly distribute the inverted index entries over the peers of the network. Because the keywords frequency in data items is usually of a zipf-distribution, simply partitioning inverted index entries by keywords would cause unbalanced loads. Furthermore, when there are more than one keywords in a query, some intermediate data have to be transmitted across the network and joined with each other to get the final result, incuring much network traffic overhead. We propose a distributed indexing scheme, called Adaptive Space Partition (ASP), that has a good load balancing and incurs little network traffic overhead. The ASP scheme is designed to work on top of the CAN DHT. A CAN network is structured as a d-dimension virtual coordinate space, where each peer node is assigned to a zone in the space. The ASP scheme maps a keyword to a region, consisting of one or more zones. Each object related to a given keyword is inserted into a peer randomly selected from the keyword’s region. To lookup objects related to the same keyword, a peer is randomly selected from the same region as a starting point, which then searches its neighborhood by flooding. Because objects with the same keyword are inserted into the same region, objects have good keyword locality and can be found easily. Furthermore, our scheme partitions inverted index entries according to the number of peers in a region to achieve better scalability. The ASP scheme also optimizes the query operation to have the same complexity as a CAN routing procedure.