Estimating frequency of change

ABSTRACT

Many online data sources are updated autonomously and independently. In this article, we make the case for estimating the change frequency of data to improve Web crawlers, Web caches and to help data mining. We first identify various scenarios, where different applications have different requirements on the accuracy of the estimated frequency. Then we develop several "frequency estimators" for the identified scenarios, showing analytically and experimentally how precise they are. In many cases, our proposed estimators predict change frequencies much more accurately and improve the effectiveness of applications. For example, a Web crawler could achieve 35% improvement in "freshness" simply by adopting our proposed estimator.

REFERENCES

• 1: Baentsch, M., Baum, L., Molter, G., Rothkugel, S., and Sturm, P. 1997. World Wide Web caching: The application-level view of the internet. IEEE Commun. 35, 6 (June), 170--178.
• 2: Bernardo, J. and Smith, A. 1994. Bayesian Theory. Wiley, New York.
• 3: Brian E. Brewington , George Cybenko, How dynamic is the Web?, Proceedings of the 9th international World Wide Web conference on Computer networks : the international journal of computer and telecommunications netowrking, p.257-276, June 2000, Amsterdam, The Netherlands
• 4: Brian E. Brewington , George Cybenko, Keeping Up with the Changing Web, Computer, v.33 n.5, p.52-58, May 2000 [doi>10.1109/2.841784]
• 5: Canavos, G. 1972. A Bayesian approach to parameter and reliability estimation in the Poisson distribution. IEEE Trans. Reliab. R21, 52--56.
• 6: Junghoo Cho , Hector Garcia-Molina, The Evolution of the Web and Implications for an Incremental Crawler, Proceedings of the 26th International Conference on Very Large Data Bases, p.200-209, September 10-14, 2000
• 7: Junghoo Cho , Hector Garcia-Molina, Synchronizing a database to improve freshness, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.117-128, May 15-18, 2000, Dallas, Texas, United States
• 8: Cho, J. and Garcia-Molina, H. 2002c. Estimating frequency of change. Tech. Rep., Univ. California, Los Angeles, Calif.
• 9: Coffman, Jr., E., Liu, Z., and Weber, R. R. 1998. Optimal robot scheduling for web search engines. J. Sched. 1, 1 (June), 15--29.
• 10: Courant, R. and David, H. 1989. Methods of mathematical physics, 1st ed. Wiley, New York.
• 11: Douglis, F., Feldmann, A., Krishnamurthy, B., and Mogul, J. 1999. Rate of change and other metrics: a live study of the world wide web. In USENIX Symposium on Internetworking Technologies and Systems.
• 12: Jenny Edwards , Kevin McCurley , John Tomlin, An adaptive model for optimizing performance of an incremental web crawler, Proceedings of the 10th international conference on World Wide Web, p.106-113, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.371960]
• 13: Gwertzman, J. and Seltzer, M. 1996. World-Wide Web cache consistency. In Proceedings of USENIX 1996 Annual Technical Conference.
• 14: Hammer, J., Garcia-Molina, H., Widom, J., Labio, W. J., and Zhuge, Y. 1995. The Stanford data warehousing project. IEEE Data Eng. Bull. 18, 2 (June), 40--47.
• 15: Venky Harinarayan , Anand Rajaraman , Jeffrey D. Ullman, Implementing data cubes efficiently, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.205-216, June 04-06, 1996, Montreal, Quebec, Canada
• 16: Lee, P. M. 1997. Bayesian Statistics: An Introduction, 2nd ed. Arnold.
• 17: Matloff, N. 2002. Estimation of internet file-access/modification rates from incomplete data. Tech. Rep., University of California, Davis, Calif.
• 18: Misra, P. and Sorenson, H. 1975. Parameter estimation in Poisson processes. IEEE Trans. Inf. Theory IT-21, 87--90.
• 19: Snyder, D. L. 1975. Random Point Processes. Wiley, New York.
• 20: Taylor, H. M. and Karlin, S. 1998. An Introduction to Stochastic Modeling, 3rd ed. Academic Press, Orlando, Fla.
• 21: Thomas, Jr., G. B. 1969. Calculus and Analytic Geometry, 4th ed. Addison-Wesley, Reading, Mass.
• 22: Wackerly, D. D., Mendenhall, W., and Scheaffer, R. L. 1997. Mathematical Statistics with Applications, 5th ed. PWS Publishing.
• 23: Craig E. Wills , Mikhail Mikhailov, Towards a better understanding of Web resources and server responses for improved caching, Proceeding of the eighth international conference on World Wide Web, p.1231-1243, May 1999, Toronto, Canada
• 24: Winkler, R. L. 1972. An Introduction to Bayesian Inference and Decision. Holt, Rinehart and Winston, Inc.
• 25: Alec Wolman , M. Voelker , Nitin Sharma , Neal Cardwell , Anna Karlin , Henry M. Levy, On the scale and performance of cooperative Web proxy caching, Proceedings of the seventeenth ACM symposium on Operating systems principles, p.16-31, December 12-15, 1999, Charleston, South Carolina, United States
• 26: Soumaya Yacout , Yusuo Chang, Using control charts for parameter estimation of a homogeneous Poisson process, Proceedings of the 19th international conference on Computers and industrial engineering, p.269-271, October 1996, Miami, Florida, United States
• 27: Haobo Yu , Lee Breslau , Scott Shenker, A scalable Web cache consistency architecture, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.163-174, August 30-September 03, 1999, Cambridge, Massachusetts, United States
• 28: Yue Zhuge , Héctor García-Molina , Joachim Hammer , Jennifer Widom, View maintenance in a warehousing environment, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.316-327, May 22-25, 1995, San Jose, California, United States

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Time series analysis

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Distributed databases

General Terms:
Algorithms, Design, Measurement

Keywords:
Change frequency estimation, Poisson process