On efficiency in searching networks
Journal
IEEE INFOCOM
Journal Volume
2
Pages
1490-1501
Date Issued
2005
Author(s)
Wang, H.
Abstract
This paper deliberates on various critical aspects in evaluating searching networks. Existing metrics either draw biased conclusions regarding search performance or provide wrong guidelines for algorithm design. We, therefore, define a unified criterion, Search Efficiency (SE), to objectively address search performance in a comprehensive manner. The goal of SE is to better characterize performance of searching networks than existing metrics do as well as to guide the design of future ones. We first validate the correctness of SE in performance evaluation in an ideal graph, strictly binary tree, by analyzing SE for two typical search methods, breadth first search and random walk. We further show its strength in performance characterization in the real-world topology, power-law random graph, under various network conditions. We finally design an algorithm, dynamic search, based on SE analysis. Its proved outstanding performance demonstrates the strength of SE to provide guidance for the future design of searching networks. © 2005 IEEE.
Subjects
Complex networks; Peer-to-peer networks; Performance evaluation; Search algorithms
SDGs
Other Subjects
Complex networks; Peer-to-peer networks; Performance evaluation; Search algorithms; Algorithms; Performance; Random processes; Topology; Trees (mathematics); Telecommunication networks
Type
conference paper
File(s)![Thumbnail Image]()
Loading...
Name
01498384.pdf
Size
2.22 MB
Format
Adobe PDF
Checksum
(MD5):38977c0c16993b329f07453879620f2a