Distributed hash tables (DHTs) are very efficient for querying based on key lookups.
However, building huge term indexes, as required for IR-style keyword search, poses a scalability
challenge for plain DHTs. Due to the large sizes of document term vocabularies, peers joining the
network cause huge amounts of key inserts and, consequently, a large number of index
maintenance messages. Thus, the key to exploiting DHTs for distributed information retrieval is to
reduce index maintenance costs. Various approaches in this direction have been pursued,
including the use of hybrid infrastructures, or changing the granularity of the inverted index to peer
level. We show that indexing costs can be significantly reduced further by letting peers form groups
in a self-organized fashion. Instead of each individual peer submitting index information separately,
all peers of a group cooperate to publish the index updates to the DHT in batches. Our evaluation
shows that this approach reduces index maintenance cost by an order of magnitude, while still
keeping a complete and correct term index for query processing.
Computer Networks 54(12): 2019-2040 (2010)