Modeling and managing changes in text databases

ABSTRACT

Large amounts of (often valuable) information are stored in web-accessible text databases. “Metasearchers” provide unified interfaces to query multiple such databases at once. For efficiency, metasearchers rely on succinct statistical summaries of the database contents to select the best databases for each query. So far, database selection research has largely assumed that databases are static, so the associated statistical summaries do not evolve over time. However, databases are rarely static and the statistical summaries that describe their contents need to be updated periodically to reflect content changes. In this article, we first report the results of a study showing how the content summaries of 152 real web databases evolved over a period of 52 weeks. Then, we show how to use “survival analysis” techniques in general, and Cox's proportional hazards regression in particular, to model database changes over time and predict when we should update each content summary. Finally, we exploit our change model to devise update schedules that keep the summaries up to date by contacting databases only when needed, and then we evaluate the quality of our schedules experimentally over real web databases.

REFERENCES

• 1: Bergman, M. K. 2001. The deep web: Surfacing hidden value. J. Electron. Pub. 7, 1 (Aug.).
• 2: 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
• 3: 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 ]
• 4: Callan, J. P. 2000. Distributed information retrieval. In Adv. Inf. Retriev. Kluwer Academic Publishers, 127--150.
• 5: Jamie Callan , Margaret Connell, Query-based sampling of text databases, ACM Transactions on Information Systems (TOIS), v.19 n.2, p.97-130, April 2001 [doi>10.1145/382979.383040]
• 6: Chakrabarti, S. 2002. Mining the web. Morgan-Kaufmann, San Francisco, CA.
• 7: 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
• 8: Junghoo Cho , Hector Garcia-Molina, Estimating frequency of change, ACM Transactions on Internet Technology (TOIT), v.3 n.3, p.256-290, August 2003 [doi>10.1145/857166.857170]
• 9: 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
• 10: Junghoo Cho , Alexandros Ntoulas, Effective change detection using sampling, Proceedings of the 28th international conference on Very Large Data Bases, p.514-525, August 20-23, 2002, Hong Kong, China
• 11: Coffman, Jr., E. G., Liu, Z., and Weber, R. R. 1998. Optimal robot scheduling for web search engines. J. Sched. 1, 1 (June), 15--29.
• 12: Cox, D. R. 1972. Regression models and life-tables (with discussion). J. Roy. Stat. Soc. B, 34, 187--220.
• 13: Fred Douglis , Anja Feldmann , Balachander Krishnamurthy , Jeffrey Mogul, Rate of change and other metrics: a live study of the world wide web, Proceedings of the USENIX Symposium on Internet Technologies and Systems on USENIX Symposium on Internet Technologies and Systems, p.14-14, December 08-11, 1997, Monterey, California
• 14: Richard O. Duda , Peter E. Hart , David G. Stork, Pattern Classification (2nd Edition), Wiley-Interscience, 2000
• 15: 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]
• 16: Dennis Fetterly , Mark Manasse , Marc Najork , Janet Wiener, A large-scale study of the evolution of web pages, Proceedings of the 12th international conference on World Wide Web, May 20-24, 2003, Budapest, Hungary [doi>10.1145/775152.775246]
• 17: Luis Gravano , Chen-Chuan K. Chang , Héctor García-Molina , Andreas Paepcke, STARTS: Stanford proposal for Internet meta-searching, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.207-218, May 11-15, 1997, Tucson, Arizona, United States
• 18: Luis Gravano , Héctor García-Molina , Anthony Tomasic, GlOSS: text-source discovery over the Internet, ACM Transactions on Database Systems (TODS), v.24 n.2, p.229-264, June 1999 [doi>10.1145/320248.320252]
• 19: Luis Gravano , Panagiotis G. Ipeirotis , Mehran Sahami, QProber: A system for automatic classification of hidden-Web databases, ACM Transactions on Information Systems (TOIS), v.21 n.1, p.1-41, January 2003 [doi>10.1145/635484.635485]
• 20: Hastie, T., Tibshirani, R., and Friedman, J. H. 2001. The Elements of Statistical Learning. Springer-Verlag, New York.
• 21: Panagiotis G. Ipeirotis , Luis Gravano, Distributed search over the hidden web: hierarchical database sampling and selection, Proceedings of the 28th international conference on Very Large Data Bases, p.394-405, August 20-23, 2002, Hong Kong, China
• 22: Panagiotis G. Ipeirotis , Alexandros Ntoulas , Junghoo Cho , Luis Gravano, Modeling and Managing Content Changes in Text Databases, Proceedings of the 21st International Conference on Data Engineering, p.606-617, April 05-08, 2005 [doi>10.1109/ICDE.2005.91]
• 23: Frederick Jelinek, Statistical methods for speech recognition, MIT Press, Cambridge, MA, 1998
• 24: Lipyeow Lim , Min Wang , Sriram Padmanabhan , Jeffrey Scott Vitter , Ramesh C. Agarwal, Characterizing Web Document Change, Proceedings of the Second International Conference on Advances in Web-Age Information Management, p.133-144, July 09-11, 2001
• 25: Marques De Sá, J. P. 2003. Applied Statistics. Springer-Verlag, New York.
• 26: Moré, J. J. 1977. The Levenberg-Marquardt algorithm: Implementation and theory. In Numerical Analysis, Lecture Notes in Mathematics vol. 630, Springer-Verlag, New York. 105--116.
• 27: Alexandros Ntoulas , Junghoo Cho , Christopher Olston, What's new on the web?: the evolution of the web from a search engine perspective, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988674]
• 28: Chris Olston , Jennifer Widom, Best-effort cache synchronization with source cooperation, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564701]
• 29: Sandeep Pandey , Christopher Olston, User-centric Web crawling, Proceedings of the 14th international conference on World Wide Web, May 10-14, 2005, Chiba, Japan [doi>10.1145/1060745.1060805]
• 30: Luo Si , Jamie Callan, Relevant document distribution estimation method for resource selection, Proceedings of the 26th annual international ACM SIGIR conference on Research and development in informaion retrieval, July 28-August 01, 2003, Toronto, Canada [doi>10.1145/860435.860490]
• 31: Stablein, D. M., Carter, Jr., W. H., and Novak, J. W. 1981. Analysis of survival data with nonproportional hazard functions. Cont. Clin. Trials 2, 2 (June), 149--159.
• 32: Craig E. Wills , Mikhail Mikhailov, Towards a better understanding of Web resources and server responses for improved caching, Proceedings of the eighth international conference on World Wide Web, p.1231-1243, May 1999, Toronto, Canada
• 33: J. L. Wolf , M. S. Squillante , P. S. Yu , J. Sethuraman , L. Ozsen, Optimal crawling strategies for web search engines, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511465]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Textual databases

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Distributed databases
      H.2.5 Heterogeneous Databases
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Abstracting methods; Indexing methods
      H.3.3 Information Search and Retrieval
          Subjects: Selection process; Search process; Information filtering; Clustering
      H.3.4 Systems and Software
          Subjects: Information networks; Performance evaluation (efficiency and effectiveness)
      H.3.5 On-line Information Services
          Subjects: Web-based services
      H.3.6 Library Automation
          Subjects: Large text archives
      H.3.7 Digital Libraries

General Terms:
Algorithms, Experimentation, Measurement, Performance

Keywords:
Metasearching, distributed information retrieval, text database selection