In-network estimation of frequency moments
Tóm tắt
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.
Tài liệu tham khảo
Alon, N., Matias, Y., Szegedy, M.: The space complexity of approximating the frequency moments. In: Proceedings of the 28th Annual ACM Symposium on the Theory of Computing STOC, pp. 20–29 (1996)
Ayaso, O., Shah, D., Dahleh, M.A.: Counting bits for distributed function computation. In: Proceedings of ISIT, pp. 652–656 (2008)
Boyd, S., Ghosh, A., Prabhakar, B., Shah, D.: Gossip algorithms: design, analysis and applications. In: Proceedings of IEEE INFOCOM, pp. 1653–1664. Miami (2005)
Cohen E (1997) Size-estimation framework with applications to transitive closure and reachability. J. Comput. Syst. Sci. 55(3):441–453
Cohen, E., Kaplan, H.: Summarizing data using bottom-k sketches. In: Proceedings of Principles of Distributed Computing, pp. 225–234 (2007)
Coppersmith, D., Kumar, R.: An improved data stream algorithm for frequency moments. In: Proceedings of 15th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 151–156 (2004)
Dutta, C., Kanoria, Y., Manjunath, D., Radhakrishnan, J.: A tight lower bound for parity in noisy communication networks. In: Proceedings Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1056–1065. San Francisco (2008)
Ganguly, S.: Estimating frequency moments of data streams using random linear combinations. In: APPROX-RANDOM, pp. 369–380 (2004)
Giridhar A, Kumar PR (2005) Computing and communicating functions over sensor networks.IEEE J. Sel. Areas Commun. 23(4):755–764
Giridhar A, Kumar PR (2006) Toward a theory of in-network computation in wireless sensor networks. IEEE Commun. Mag. 44(4):98–107
Gupta, P., Kumar, P.R.: Critical power for asymptotic connectivity in wireless networks. In: Stochastic Analysis, Control, Optimization and Applications: A Volume in Honor of W. H. Fleming. Birkhauser, Boston (1998)
Kamath, S., Manjunath, D.: On distributed function computation in structure-free random networks. In: Proceedings of IEEE ISIT. Toronto (2008)
Mosk-Aoyama, D., Shah, D.: Computing separable functions via gossip. In: Proceedings of 22nd ACM Symposium on Principles of Distributed Computing (PODC), pp. 113–122 (2006)
Motwani R, Raghavan P (1996) Randomized algorithms. ACM Comput. Surv. 28(1):33–37. doi:10.1145/234313.234327 . http://doi.acm.org/10.1145/234313.234327URL
Muthukrishnan, S.: Data streams: Algorithms and applications. Volume 1, Number 2 of Foundations and Trends in Theoretical Computer Science. now publishers (2005)
Nelson, J.: Sketching and Streaming High-Dimensional Vectors. Massachusetts Institute of Technology, Department of Electrical Engineering and Computer Science (2011). http://books.google.co.in/books?id=SsAeuAAACAAJ
Penrose, M.: Random Geometric Graphs. Oxford University Press, Oxford (2003)
S. K. Iyer, D.M., Sundaresan, R.: In-network computation in random wireless networks at constant refresh rates with lower energy costs: A PAC approach. IEEE Trans. Mobile Comput. 10(1), 146–155 (2011)
Shah D (2009) Gossip algorithms. Found. Trends Netw. 3(1):1–125