Efficient estimation algorithms for neighborhood variance and other moments

ABSTRACT

The neighborhood variance problem is as follows. Given a (directed or undirected) graph with values associated with each node, compute a data structure that for any given node v and r ≥ 0, would quickly produce an estimate of the variance of all values of nodes that lie within distance r from v. The problem can be generalized to other moment functions and to arbitrary distance-dependent decay.These problems are motivated by applications where the relevance of a measurement observed (or data present) at a certain location decreases with its distance, and thus the aggregate value varies by location. The centralized version of the problem is motivated by applications to query processing on graphical databases. The distributed version of the problem falls in a model we recently introduced for spatially decaying aggregation and is motivated by sensor or p²p networks.We present novel algorithms for the centralized and distributed versions of the problem. Our algorithms are nearly optimal, the centralized version requires Õ(m) time and the distributed version requires polylogarithmic communication per node or edge (depending on assumptions).

REFERENCES

• 1: Brian Babcock , Shivnath Babu , Mayur Datar , Rajeev Motwani , Jennifer Widom, Models and issues in data stream systems, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543615]
• 2: Brain Babcock , Mayur Datar , Rajeev Motwani , Liadan O'Callaghan, Maintaining variance and k-medians over data stream windows, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.234-243, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773176]
• 3: Moses Charikar , Liadan O'Callaghan , Rina Panigrahy, Better streaming algorithms for clustering problems, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780548]
• 4: Edith Cohen, Size-estimation framework with applications to transitive closure and reachability, Journal of Computer and System Sciences, v.55 n.3, p.441-453, Dec. 1997 [doi>10.1006/jcss.1997.1534]
• 5: E. Cohen and H. Kaplan. Spatially-decaying aggregation over a network: model and algorithms. In preparation, 2003.
• 6: Edith Cohen , Martin Strauss, Maintaining time-decaying stream aggregates, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.223-233, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773175]
• 7: Mayur Datar , Aristides Gionis , Piotr Indyk , Rajeev Motwani, Maintaining Stream Statistics over Sliding Windows, SIAM Journal on Computing, v.31 n.6, p.1794-1813, 2002 [doi>10.1137/S0097539701398363]
• 8: Phillip B. Gibbons , Srikanta Tirthapura, Distributed streams algorithms for sliding windows, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada [doi>10.1145/564870.564880]
• 9: I. A. Gradshteyn and I. M. Ryzhik. Tables of Integrals, Series, and products. Academic Press, San Diego, CA, 6 edition, 2000.
• 10: A. Papoulis. Probability, Random Variables, and Stochastic Processes. McGraw-Hill Book Company, New York, second edition, 1984.