Multi-dimensional online tracking

ABSTRACT

We propose and study a new class of online problems, which we call online tracking. Suppose an observer, say Alice, observes a multi-valued function f: Z⁺ → Z^d overtime in an online fashion, i.e., she only sees f(t) for t ≤ t_now where t_now is the current time. She would like to keep a tracker, say Bob, informed of the current value of f at all times. Under this setting, Alice could send new values of f to Bob from time to time, so that the current value of f is always within a distance of Δ to the last value received by Bob. We give competitive online algorithms whose communication costs are compared with the optimal offline algorithm that knows the entire f in advance. We also consider variations of the problem where Alice is allowed to send "predictions" to Bob, to further reduce communication for well-behaved functions. These online tracking problems have a variety of application ranging from sensor monitoring, location-based services, to publish/subscribe systems.

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: Alastair R. Beresford , Frank Stajano, Location Privacy in Pervasive Computing, IEEE Pervasive Computing, v.2 n.1, p.46-55, January 2003 [doi>10.1109/MPRV.2003.1186725]
• 3: Dimitris Bertsimas , Santosh Vempala, Solving convex programs by random walks, Journal of the ACM (JACM), v.51 n.4, p.540-556, July 2004 [doi>10.1145/1008731.1008733]
• 4: Badrish Chandramouli , Jeff M. Phillips , Jun Yang, Value-based notification conditions in large-scale publish/subscribe systems?, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 5: K. L. Clarkson , David Eppstein , Gary L. Miller , Carl Sturtivant , Shang-Hua Teng, Approximating center points with iterated radon points, Proceedings of the ninth annual symposium on Computational geometry, p.91-98, May 18-21, 1993, San Diego, California, United States [doi>10.1145/160985.161004]
• 6: Graham Cormode , Minos Garofalakis, Sketching streams through the net: distributed approximate query tracking, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 7: Graham Cormode , Minos Garofalakis , S. Muthukrishnan , Rajeev Rastogi, Holistic aggregates in a networked world: distributed tracking of approximate quantiles, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066161]
• 8: Graham Cormode , S. Muthukrishnan , Ke Yi, Algorithms for distributed functional monitoring, Proceedings of the nineteenth annual ACM-SIAM symposium on Discrete algorithms, p.1076-1085, January 20-22, 2008, San Francisco, California
• 9: S. Davis, J. Edmonds, and R. Impagliazzo1. Online algorithms to minimize resource reallocations and network communication. In APPROX and RANDOM, 2006.
• 10: Amol Deshpande , Carlos Guestrin , Samuel R. Madden , Joseph M. Hellerstein , Wei Hong, Model-driven data acquisition in sensor networks, Proceedings of the Thirtieth international conference on Very large data bases, p.588-599, August 31-September 03, 2004, Toronto, Canada
• 11: Yanlei Diao , Shariq Rizvi , Michael J. Franklin, Towards an internet-scale XML dissemination service, Proceedings of the Thirtieth international conference on Very large data bases, p.612-623, August 31-September 03, 2004, Toronto, Canada
• 12: B. Grunbaum. Partitions of mass-distributions and of convex bodies by hyperplanes. Pacific J. Math, 1960.
• 13: Ram Keralapura , Graham Cormode , Jeyashankher Ramamirtham, Communication-efficient distributed monitoring of thresholded counts, Proceedings of the 2006 ACM SIGMOD international conference on Management of data, June 27-29, 2006, Chicago, IL, USA [doi>10.1145/1142473.1142507]
• 14: B. Korte and J. Vygen. Combinatorial Optimization: Theory and Algorithms. Springer-Verlag, 4th edition, 2007.
• 15: Samuel R. Madden , Michael J. Franklin , Joseph M. Hellerstein , Wei Hong, TinyDB: an acquisitional query processing system for sensor networks, ACM Transactions on Database Systems (TODS), v.30 n.1, p.122-173, March 2005 [doi>10.1145/1061318.1061322]
• 16: Jiri Matousek, Lectures on Discrete Geometry, Springer-Verlag New York, Inc., Secaucus, NJ, 2002
• 17: Chris Olston , Boon Thau Loo , Jennifer Widom, Adaptive precision setting for cached approximate values, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.355-366, May 21-24, 2001, Santa Barbara, California, United States
• 18: Joseph O'Rourke, An on-line algorithm for fitting straight lines between data ranges, Communications of the ACM, v.24 n.9, p.574-578, Sept. 1981 [doi>10.1145/358746.358758]
• 19: G. J. Pottie , W. J. Kaiser, Wireless integrated network sensors, Communications of the ACM, v.43 n.5, p.51-58, May 2000 [doi>10.1145/332833.332838]
• 20: Luis A. Rademacher, Approximating the centroid is hard, Proceedings of the twenty-third annual symposium on Computational geometry, June 06-08, 2007, Gyeongju, South Korea [doi>10.1145/1247069.1247123]
• 21: Jochen Schiller , Agnès Voisard, Location Based Services, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2004
• 22: Andrew Chi-Chih Yao, Some complexity questions related to distributive computing(Preliminary Report), Proceedings of the eleventh annual ACM symposium on Theory of computing, p.209-213, April 30-May 02, 1979, Atlanta, Georgia, United States [doi>10.1145/800135.804414]
• 23: Y. Yao and J. Gehrke. Query processing for sensor networks. In CIDR, 2003.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Online computation