We consider a network of autonomous peers forming a logically global but physically distributed search engine, where every peer has its own local collection generated by independently crawling the Web. A challenging task in such systems is to efficiently route user queries to peers that am deliver high quality results and be able to rank these returned results, thus satisfying the users' information need. However, the problem inherent with this scenario is selecting a few promising peers out of an a priori unlimited number of peers. In recent research a rather strict notion of semantic overlay networks has been established. In most approaches, peers are connected to other peers based on a rigid semantic profile by clustering them based on their contents. In contrast, our strategy follows the spirit of peer autonomy and creates semantic overlay networks based on the notion of "peer-to-peer dating". Peers arc free to decide which connections they create and which they want to avoid based on various usefulness estimators. The proposed techniques can be easily integrated into existing systems as they require only small additional bandwidth consumption as most messages can be piggybacked onto established communication. We show how we can greatly benefit from these additional semantic relations during query routing in search engines, such as Minerva, and in the JXP algorithm, which computes the PageRank authority measure in a completely decentralized manner. (c) 2006 Elsevier Ltd. All rights reserved.
