Node sampling using random centrifugal walks

Sevilla de Pablo, Andrés; Mozo Velasco, Bonifacio Alberto y Fernández Anta, Antonio (2012). Node sampling using random centrifugal walks. En: "16th International Conference On Principles of Distributed Systems (OPODIS 2012)- December 17th-20th", 17/12/2012 - 20/12/2012, Roma, Italia. ISBN 978-3-642-35475-5. pp. 300-314. https://doi.org/10.1007/978-3-642-35476-2_21.

Descripción

Título: Node sampling using random centrifugal walks
Autor/es:
  • Sevilla de Pablo, Andrés
  • Mozo Velasco, Bonifacio Alberto
  • Fernández Anta, Antonio
Tipo de Documento: Ponencia en Congreso o Jornada (Artículo)
Título del Evento: 16th International Conference On Principles of Distributed Systems (OPODIS 2012)- December 17th-20th
Fechas del Evento: 17/12/2012 - 20/12/2012
Lugar del Evento: Roma, Italia
Título del Libro: Principles of Distributed Systems
Fecha: 2012
ISBN: 978-3-642-35475-5
Volumen: Lectur
Materias:
Escuela: E.U. de Informática (UPM) [antigua denominación]
Departamento: Informática Aplicada [hasta 2014]
Licencias Creative Commons: Reconocimiento - Sin obra derivada - No comercial

Texto completo

[img]
Vista Previa
PDF (Document Portable Format) - Se necesita un visor de ficheros PDF, como GSview, Xpdf o Adobe Acrobat Reader
Descargar (1MB)

Resumen

Sampling a network with a given probability distribution has been identified as a useful operation. In this paper we propose distributed algorithms for sampling networks, so that nodes are selected by a special node, called the source, with a given probability distribution. All these algorithms are based on a new class of random walks, that we call Random Centrifugal Walks (RCW). A RCW is a random walk that starts at the source and always moves away from it. Firstly, an algorithm to sample any connected network using RCW is proposed. The algorithm assumes that each node has a weight, so that the sampling process must select a node with a probability proportional to its weight. This algorithm requires a preprocessing phase before the sampling of nodes. In particular, a minimum diameter spanning tree (MDST) is created in the network, and then nodes weights are efficiently aggregated using the tree. The good news are that the preprocessing is done only once, regardless of the number of sources and the number of samples taken from the network. After that, every sample is done with a RCW whose length is bounded by the network diameter. Secondly, RCW algorithms that do not require preprocessing are proposed for grids and networks with regular concentric connectivity, for the case when the probability of selecting a node is a function of its distance to the source. The key features of the RCW algorithms (unlike previous Markovian approaches) are that (1) they do not need to warm-up (stabilize), (2) the sampling always finishes in a number of hops bounded by the network diameter, and (3) it selects a node with the exact probability distribution.

Más información

ID de Registro: 20806
Identificador DC: http://oa.upm.es/20806/
Identificador OAI: oai:oa.upm.es:20806
Identificador DOI: 10.1007/978-3-642-35476-2_21
URL Oficial: http://opodis2012.dis.uniroma1.it/
Depositado por: Memoria Investigacion
Depositado el: 27 Sep 2013 17:39
Ultima Modificación: 22 Sep 2014 11:21
  • Open Access
  • Open Access
  • Sherpa-Romeo
    Compruebe si la revista anglosajona en la que ha publicado un artículo permite también su publicación en abierto.
  • Dulcinea
    Compruebe si la revista española en la que ha publicado un artículo permite también su publicación en abierto.
  • Recolecta
  • e-ciencia
  • Observatorio I+D+i UPM
  • OpenCourseWare UPM