A Hierarchical Semantic Overlay Approach to P2P Similarity Search

One of the most important problems in information retrieval is similarity search. Informally, the problem is: given a similarity query, which can be a point query or a range query, we need to return a set of contents that are most relevant to the search criteria according to some semantic distance function. We propose EZSearch, a decentralized solution to this problem in the context of Peer-to-Peer (P2P) networks. EZSearch features the following for a network of N users. First, queries can be answered with O(log_kN) worst-case search time and low search overhead. Second, to maintain the hierarchy, a node keeps track of only O(k) other nodes and failure recovery requires no more than O(k) reconnections; these overheads are independent of the network size. Last but not least, the number of objects whose indices are stored at remote nodes is small and, therefore, so are the costs of index migration, storage, and validity.