Paper Info
Title
In-Network Estimation of Frequency Moments
Abstract
We consider the problem of estimating functions of distributed data using a distributed algorithm over a network. The extant literature on computing functions in distributed networks such as wired and wireless sensor networks and peer-to-peer networks deals with computing linear functions of the distributed data when the alphabet size of the data values is small, O(1). We describe a distributed randomized algorithm to estimate a class of non-linear functions of the distributed data which is over a large alphabet. We consider three types of networks: point-to-point networks with gossip based communication, random planar networks in the connectivity regime and random planar networks in the percolating regime both of which use the slotted Aloha communication protocol. For each network type, we estimate the scaled kth frequency moments, for k ≥ 2. Specifically, for every k ≥ 2, we give a distributed randomized algorithm that computes, with probability (1 − δ), an \(\epsilon\)-approximation of the scaled kth frequency moment, F k /N k , using time \(O(M^{1-\frac{1}{k-1}} T)\) and \(O(M^{1-\frac{1}{k-1}} \log N \log (\delta^{-1})/\epsilon^{2})\) bits of transmission per communication step. Here, N is the number of nodes in the network, T is the information spreading time and M = o(N) is the alphabet size.
Year
DOI
Venue
2012
10.1007/s12572-013-0078-2
International Journal of Advances in Engineering Sciences and Applied Mathematics
Keywords
Field
DocType
In-network computing, Frequency moments, Randomized algorithms
Binary logarithm,Randomized algorithm,Combinatorics,Frequency moments,Aloha,Distributed algorithm,Planar,Linear function,Wireless sensor network,Mathematics
Journal
Volume
Issue
ISSN
abs/1210.6134
1
0975-5616
Citations 
PageRank 
References 
0
0.34
16
Authors
3
Name
Order
Citations
PageRank
Pooja Vyavahare172.19
Nutan Limaye213420.59
D. Manjunath3677.48