Spatially-decaying aggregation over a network: model and algorithms

ABSTRACT

Data items are often associated with a location in which they are present or collected, and their relevance or influence decays with their distance. Aggregate values over such data thus depend on the observing location, where the weight given to each item depends on its distance from that location. We term such aggregation spatially-decaying.Spatially-decaying aggregation has numerous applications: Individual sensor nodes collect readings of an environmental parameter such as contamination level or parking spot availability; the nodes then communicate to integrate their readings so that each location obtains contamination level or parking availability in its neighborhood. Nodes in a p2p network could use a summary of content and properties of nodes in their neighborhood in order to guide search. In graphical databases such as Web hyperlink structure, properties such as subject of pages that can reach or be reached from a page using link traversals provide information on the page.We formalize the notion of spatially-decaying aggregation and develop efficient algorithms for fundamental aggregation functions, including sums and averages, random sampling, heavy hitters, quantiles, and L_p norms.

REFERENCES

• 1: Noga Alon , Yossi Matias , Mario Szegedy, The space complexity of approximating the frequency moments, Journal of Computer and System Sciences, v.58 n.1, p.137-147, Feb. 1999 [doi>10.1006/jcss.1997.1545]
• 2: B. Awerbuch, Randomized distributed shortest paths algorithms, Proceedings of the twenty-first annual ACM symposium on Theory of computing, p.490-500, May 14-17, 1989, Seattle, Washington, United States [doi>10.1145/73007.73054]
• 3: 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]
• 4: Terrestrial air temperature and precipitation: monthly and annual climatologies (version 3.02), 2001. http://climate.udel.edu/~climate.
• 5: 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]
• 6: E. Cohen. Structure prediction and computation of sparse matrix products. J. Combinatorial Optimization, 2:307--332, 1999.
• 7: Edith Cohen , Haim Kaplan, Efficient estimation algorithms for neighborhood variance and other moments, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 8: 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]
• 9: Open Source Community. Gnutella. In http://gnutella.wego.com/, 2001.
• 10: Arturo Crespo , Hector Garcia-Molina, Routing Indices For Peer-to-Peer Systems, Proceedings of the 22 nd International Conference on Distributed Computing Systems (ICDCS'02), p.23, July 02-05, 2002
• 11: 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]
• 12: Amol Deshpande , Suman Nath , Phillip B. Gibbons , Srinivasan Seshan, Cache-and-query for wide area sensor databases, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872818]
• 13: D. Estrin, L. Girod, G. Pottie, and M. Srivastava. Instrumenting the world with wireless sensor networks. In Proc. International Conference on Acoustics, Speech, and Signal Processing (ICASSP), 2001.
• 14: J. Feigenbaum , S. Kannan , M. Strauss , M. Viswanathan, An Approximate L1-Difference Algorithm for Massive Data Streams, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.501, October 17-18, 1999
• 15: Sally Floyd , Van Jacobson, Random early detection gateways for congestion avoidance, IEEE/ACM Transactions on Networking (TON), v.1 n.4, p.397-413, Aug. 1993 [doi>10.1109/90.251892]
• 16: Saurabh Ganeriwal , Chih Chieh Han , Mani B. Srivastava, Poster abstract: spatial average of a continuous physical process in sensor networks, Proceedings of the 1st international conference on Embedded networked sensor systems, November 05-07, 2003, Los Angeles, California, USA [doi>10.1145/958491.958529]
• 17: D. Ganesan, S. Ratnasamy, H. Wang, and D. Estrin. Coping with irregular spatio-temporal sampling in sensor networks. In Proceedings of the ACM SIGCOMM HOTNETS-II workshop, 2003.
• 18: 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]
• 19: Michael Greenwald , Sanjeev Khanna, Space-efficient online computation of quantile summaries, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.58-66, May 21-24, 2001, Santa Barbara, California, United States
• 20: L. J. Guibas, D. E. Knuth, and M. Sharir. Randomized incremental construction of Delaunay and Voronoi diagrams: Algorithmica, 7:381--413, 1992.
• 21: P. Indyk, Stable distributions, pseudorandom generators, embeddings and data stream computation, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.189, November 12-14, 2000
• 22: V. Jacobson, Congestion avoidance and control, Symposium proceedings on Communications architectures and protocols, p.314-329, August 16-18, 1988, Stanford, California, United States
• 23: David Kempe , Jon M. Kleinberg, Protocols and Impossibility Results for Gossip-Based Communication Mechanisms, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.471-480, November 16-19, 2002
• 24: David Kempe , Jon Kleinberg , Alan Demers, Spatial gossip and resource location protocols, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.163-172, July 2001, Hersonissos, Greece [doi>10.1145/380752.380796]
• 25: Flip Korn , S. Muthukrishnan, Influence sets based on reverse nearest neighbor queries, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.201-212, May 15-18, 2000, Dallas, Texas, United States
• 26: F. Korn, S. Muthukrishnana, and D. Srivastava. Reverse nearest neighbor aggregates over data streams. In Proc. of the 28th international conference on Very Large Databases (VLDB 2002). ACM, 2002.
• 27: Xuemin Lin , Hongjun Lu , Jian Xu , Jeffrey Xu Yu, Continuously Maintaining Quantile Summaries of the Most Recent N Elements over a Data Stream, Proceedings of the 20th International Conference on Data Engineering, p.362, March 30-April 02, 2004
• 28: Samuel Madden , Michael J. Franklin , Joseph M. Hellerstein , Wei Hong, TAG: a Tiny AGgregation service for Ad-Hoc sensor networks, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060303]
• 29: Alan Mainwaring , David Culler , Joseph Polastre , Robert Szewczyk , John Anderson, Wireless sensor networks for habitat monitoring, Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570738.570751]
• 30: G. S. Manku and R. Motwani. Approximate frequency counts over data streams. In Proc. of the 28th international conference on Very Large Databases (VLDB 2002), pages 346--357. ACM, 2002.
• 31: Gurmeet Singh Manku , Sridhar Rajagopalan , Bruce G. Lindsay, Approximate medians and other quantiles in one pass and with limited memory, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.426-435, June 01-04, 1998, Seattle, Washington, United States
• 32: M. R. Paterson. Progress in selection. Dept. of Computer Science, University of Warwick, Coventry, UK, 1997.
• 33: J. Zhao, R. Govindan, and D. Estrin. Computing aggregates for monitoring wireless sensor networks. In Proc. of First IEEE international Workshop on Sensor Network Protocols and Applications, 2003.