Font Size: a A A

Approximate Aggregation Of Time-Varying Data In P2P Networks Based On Uniform Sampling

Posted on:2008-07-23Degree:MasterType:Thesis
Country:ChinaCandidate:S Y ChengFull Text:PDF
GTID:2178360245997685Subject:Computer Science and Technology
Abstract/Summary:PDF Full Text Request
P2P (Peer-to-Peer) is the key technology of reconstructing the future distrib-uted architecture and has a good application perspective. With the wide and com-plex applications of P2P technologies, there will be more and more P2P systems generating the time-varying data. Because the statistical results of these data will help people to make right decisions and the aggregation processing is one of most important methods in statistics. So in this paper, we will study the aggrega-tion algorithm for time-varying data in P2P.In P2P network, due to its large scale, decentralization and dynamic proper-ties, there exists many challenge problems in constructing aggregation algorithm for time-varying data. Consider that the traditional methods cannot perform well in this field, we will do some research on it. In this paper, we focus on such as-pects as below:First, in this paper, we will use sampling method to construct aggregation algorithm in order to save time and network resource. And consider that the dy-namic property of P2P network will decrease the sampling algorithm's accuracy, so we use the total probability formula, Markov theory, Metropolis-Hastings method to discuss the feasibility of uniformly sampling in dynamic P2P network. At last we propose the algorithm-- USTPF algorithm (Uniformly Sampling based on Total Probability Formula), and it first solve the uniformly sampling problem in dynamic network. According to theoretical analysis and experimental results, it shows that all the USTPF algorithms are correct and effective.Second, we must ensure that the data used in aggregation are not out-of-date. It means that the time of collecting data of giving algorithm must be short enou-gh. In this paper we propose the AUS algorithm (Aggregation based on Uniform-ly Sampling) to achieve these aim. To our knowledge, AUS algorithm is the first method to solve the aggregation problem for time-varying data. We use central limit theorem and Chebyshev polynomials to prove the correctness of AUS alg-orithm. According to experimental results, it shows that all the AUS algorithms are correct and effective.Third, some people may be interested in the historical information of time- varying data, so we must solve the problem of storing the aggregation results of time-varying data in P2P networks. And in this paper, we advise to choose a few nodes as the recorded nodes to store aggregation results of time-varying data, and we give an algorithm called LCDS algorithm to solve the recorded nodes set choosing problem. At last, we use theoretical analysis and experimental results to show that LCDS algorithm is correct and effective.
Keywords/Search Tags:P2P, uniformly sampling, time-varying data, aggregation query
PDF Full Text Request
Related items