Header

UZH-Logo

Maintenance Infos

Fast similarity search in peer-to-peer networks


Bocek, T; Hunt, E; Hausheer, D; Stiller, B (2008). Fast similarity search in peer-to-peer networks. In: 11th IEEE/IFIP Network Operations and Management Symposium (NOMS 2008), Salvador, Brazil, 7 April 2008 - 11 April 2008. IEEE, 240-247.

Abstract

Peer-to-peer (P2P) systems show numerous advantages over centralized systems, such as load balancing, scalability, and fault tolerance, and they require certain functionality, such as search, repair, and message and data transfer. In particular, structured P2P networks perform an exact search in logarithmic time proportional to the number of peers. However, keyword similarity search in a structured P2P network remains a challenge. Similarity search for service discovery can significantly improve service management in a distributed environment. As services are often described informally in text form, keyword similarity search can find the required services or data items more reliably. This paper presents a fast similarity search algorithm for structured P2P systems. The new algorithm, called P2P fast similarity search (P2PFastSS), finds similar keys in any distributed hash table (DHT) using the edit distance metric, and is independent of the underlying P2P routing algorithm. Performance analysis shows that P2PFastSS carries out a similarity search in time proportional to the logarithm of the number of peers. Simulations on PlanetLab confirm these results and show that a similarity search with 34,000 peers performs in less than three seconds on average. Thus, P2PFastSS is suitable for similarity search in large-scale network infrastructures, such as service description matching in service discovery or searching for similar terms in P2P storage networks.

Abstract

Peer-to-peer (P2P) systems show numerous advantages over centralized systems, such as load balancing, scalability, and fault tolerance, and they require certain functionality, such as search, repair, and message and data transfer. In particular, structured P2P networks perform an exact search in logarithmic time proportional to the number of peers. However, keyword similarity search in a structured P2P network remains a challenge. Similarity search for service discovery can significantly improve service management in a distributed environment. As services are often described informally in text form, keyword similarity search can find the required services or data items more reliably. This paper presents a fast similarity search algorithm for structured P2P systems. The new algorithm, called P2P fast similarity search (P2PFastSS), finds similar keys in any distributed hash table (DHT) using the edit distance metric, and is independent of the underlying P2P routing algorithm. Performance analysis shows that P2PFastSS carries out a similarity search in time proportional to the logarithm of the number of peers. Simulations on PlanetLab confirm these results and show that a similarity search with 34,000 peers performs in less than three seconds on average. Thus, P2PFastSS is suitable for similarity search in large-scale network infrastructures, such as service description matching in service discovery or searching for similar terms in P2P storage networks.

Statistics

Citations

Dimensions.ai Metrics
5 citations in Web of Science®
9 citations in Scopus®
Google Scholar™

Altmetrics

Downloads

217 downloads since deposited on 09 Dec 2008
12 downloads since 12 months
Detailed statistics

Additional indexing

Item Type:Conference or Workshop Item (Paper), refereed, original work
Communities & Collections:03 Faculty of Economics > Department of Informatics
Dewey Decimal Classification:000 Computer science, knowledge & systems
Scopus Subject Areas:Physical Sciences > Computer Networks and Communications
Physical Sciences > Information Systems
Language:English
Event End Date:11 April 2008
Deposited On:09 Dec 2008 07:54
Last Modified:25 Jun 2022 08:37
Publisher:IEEE
Series Name:Network Operations and Management Symposium
Number:2008
ISSN:1542-1201
ISBN:978-1-4244-2065-0
Additional Information:This paper was presented at 11th IEEE/IFIP Network Operations and Management Symposium (NOMS 2008) in Salvador, Brazil, 7–11 april 2008. © 2008 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE.
OA Status:Green
Publisher DOI:https://doi.org/10.1109/NOMS.2008.4575140
Official URL:http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=4575140
  • Description: Original publication