Keyword Search In Peer-to-Peer Networks

Recent years Peer-to-Peer(P2P) networks attract the attention of the research community because of its large scale, self-organization and robustness. File sharing is one of the most important application in P2P networks, the first of which is the famous system, Napster. Due the the large scale of P2P networks, it can fully utilize the abundent resource provided by milliions of users to improve the qulity of the service. However, the large scale also leads to many challenges to the P2P file sharing systems. Especially, it makes file searching very difficult and increases the burden of the underlying networks. Therefore, it is important to investigate the efficient search mechanism in P2P networks.In this thesis, we investigate how to provide efficient keyword-based search in two major kinds of P2P networks, i.e., unstructured P2P networks and structured P2P networks. Due to the large scale of P2P networks, we focus on both improving the search effect and reducing the network overhead. Previously proposed search mechanisms only focus on the search effect or the network overhead. Our mechanisms take the tradeoff between these two aspects into consideration, achieving efficient P2P search.In unstructured P2P networks, we propose a learning based query routing protocol to obtain efficient search. Since it use the information brought by the queries and the query hits, it greatly alleviates the extra network overhead. Moverover, we leverage the dupliation of queries observed in the real P2P networks and adapt the principles of reinforcement learning to optimize the search mechanism. Compared with previous search mechanisms, this search mechanism attains both good search effect and low extra network overhead. In structured P2P networks, files are indexed on different nodes according to their keywords. To multiple keyword search, the search is realized by exchanging the file lists corresponding to various keywords among nodes to find those containing all these keywords. Since the size of file list corresponding to a certain keyword is very large,the network overhead is also very heavy. Through the analysis we find that the size of the intersection of multiple sets is determined by the properties of these sets. If we can find a proper intersection sequence, the network overhead will be seriously reduced. In this paper, we propose such a scheduling mechanism to reduce the network overhead of multiple keyword search in structured networks.