USENIX 2005 Annual Technical Conference, General Track Abstract
Pp. 355358 of the Proceedings
A Hierarchical Semantic Overlay Approach to P2P Similarity Search
Duc A. Tran, University of Dayton
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(logkN) 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.
- View the full text of this paper in HTML and PDF.
Until April 2006, you will need your USENIX membership identification in order to access the full papers. The Proceedings are published as a collective work, © 2005 by the USENIX Association. All Rights Reserved. Rights to individual papers remain with the author or the author's employer. Permission is granted for the noncommercial reproduction of the complete work for educational or research purposes. USENIX acknowledges all trademarks within this paper.
- If you need the latest Adobe Acrobat Reader, you can download it from Adobe's site.