Improving resource location with locally precomputed partial random walks
Impacto
![Google Scholar](/xmlui/themes/Mirage2/images/uji/logo_google.png)
![Microsoft Academico](/xmlui/themes/Mirage2/images/uji/logo_microsoft.png)
Metadatos
Mostrar el registro completo del ítemcomunitat-uji-handle:10234/9
comunitat-uji-handle2:10234/7038
comunitat-uji-handle3:10234/8634
comunitat-uji-handle4:
INVESTIGACIONEste recurso está restringido
http://dx.doi.org/10.1007/s00607-013-0353-x |
Metadatos
Título
Improving resource location with locally precomputed partial random walksFecha de publicación
2015-09Editor
Springer ViennaISSN
0010-485X; 1436-5057Tipo de documento
info:eu-repo/semantics/articleVersión de la editorial
http://link.springer.com/article/10.1007%2Fs00607-013-0353-xPalabras clave / Materias
Resumen
Random walks can be used to search complex networks for a desired resource. To reduce search lengths, we propose a mechanism based on building random walks connecting together partial walks (PW) previously computed ... [+]
Random walks can be used to search complex networks for a desired resource. To reduce search lengths, we propose a mechanism based on building random walks connecting together partial walks (PW) previously computed at each network node. Resources found in each PW are registered. Searches can then jump over PWs where the resource is not located. However, we assume that perfect recording of resources may be costly, and hence, probabilistic structures like Bloom filters are used. Then, unnecessary hops may come from false positives at the Bloom filters. Two variations of this mechanism have been considered, depending on whether we first choose a PW in the current node and then check it for the resource, or we first check all PWs and then choose one. In addition, PWs can be either simple random walks or self-avoiding random walks. Analytical models are provided to predict expected search lengths and other magnitudes of the resulting four mechanisms. Simulation experiments validate these predictions and allow us to compare these techniques with simple random walk searches, finding very large reductions of expected search lengths. [-]
Publicado en
Computing, 2015, vol. 97, núm. 9Derechos de acceso
© Springer-Verlag Wien 2013
© Springer International Publishing AG, Part of Springer Science+Business Media
"The final publication is available at Springer via http://dx.doi.org/10.1007/s00607-013-0353-x"
http://rightsstatements.org/vocab/InC/1.0/
info:eu-repo/semantics/restrictedAccess
http://rightsstatements.org/vocab/InC/1.0/
info:eu-repo/semantics/restrictedAccess
Aparece en las colecciones
- LSI_Articles [362]