Improving resource location with locally precomputed partial random walks

DOI10.1007/S00607-013-0353-XMaRDI QIDQ497106zbMATH OpenOpenAlexFDO

Authors Yong-Cai Geng, Sumit K. Garg

Publication date 23 September 2015

Published in Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1304.5100

zbMATH Keywords

partial random walksrandom walksresource locationsearch lengthself-avoiding random walks

Mathematics Subject Classification ID

Sums of independent random variables; random walks (60G50) Network design and communication in computer systems (68M10) Distributed systems (68M14) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Abstract: 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.

Recommendations

• Randomized local search for the discrete competitive facility location problem
• The stochastic walk algorithms for point location in pseudo-triangulations
• An iterated local search for solving a location-routing problem
• Speeding up random walks with neighborhood exploration
• Local search based approximation algorithms for two-stage stochastic location problems
• A new local search for continuous location problems
• Efficient search by optimized intermittent random walks
• scientific article; zbMATH DE number 1058967

Cites work

• A model of self-avoiding random walks for searching complex networks
• Distributed random walks
• Network Applications of Bloom Filters: A Survey
• Performance of random walks in one-hop replication networks

Cited in

(5)

• Random walk search in unstructured P2P
• A model of self-avoiding random walks for searching complex networks
• Numerical evaluation of the random walk search algorithm
• Optimizing random walk search algorithms in P2P networks
• Performance of random walks in one-hop replication networks

This page was built for publication: Improving resource location with locally precomputed partial random walks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q497106)