Abstract | ||
---|---|---|
Flooding and random walk are two basic mechanisms for blind search in unstructured peer-to-peer overlays. Although these mechanisms have been widely studied experimentally and via simulations, they have not been analytically modeled. Time overhead, message overhead, and success rate are often used as metrics for search schemes. This paper shows that node coverage is an important metric to estimate performance metrics such as the message efficiency, success rate, and object recall of a blind search. The paper then presents two simple models to analyze node coverage in random graph overlays. These models are useful to set query parameters, evaluate search efficiency, and to estimate object replication on a statistical basis. |
Year | DOI | Venue |
---|---|---|
2006 | 10.1109/NCA.2006.14 | NCA |
Keywords | Field | DocType |
search scheme,object recall,success rate,blind search,message efficiency,unstructured overlays,node coverage,message overhead,search efficiency,analysis models,performance metrics,object replication,information retrieval,random walk,graph theory,measurement,network topology,random graph | Graph theory,Query string,Random graph,Random walk,Computer science,Keyword search,Network topology,Theoretical computer science,Overlay,Analysis models,Distributed computing | Conference |
ISBN | Citations | PageRank |
0-7695-2640-3 | 4 | 0.46 |
References | Authors | |
7 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Bin Wu | 1 | 17 | 1.81 |
Ajay D. Kshemkalyani | 2 | 979 | 76.27 |