Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

We introduce and theoretically study the Gardener's problem that well models many web information monitoring scenarios, where numerous dynamically changing web sources are monitored and local information needs to be periodically updated under communication and computation capacity constraints. Typical such examples include maintenance of inverted indexes for search engines and maintenance of extracted structures for unstructured data management systems. We formulate a corresponding multicriteria optimization problem and propose heuristic solutions.

REFERENCES

• 1: Amotz Bar-Noy , Randeep Bhatia , Joseph (Seffi) Naor , Baruch Schieber, Minimizing Service and Operation Costs of Periodic Scheduling, Mathematics of Operations Research, v.27 n.3, p.518-544, August 2002 [doi>10.1287/moor.27.3.518.314]
• 2: Amotz Bar-Noy , Richard E. Ladner , Tami Tamir, Windows scheduling as a restricted version of bin packing, ACM Transactions on Algorithms (TALG), v.3 n.3, p.28-es, August 2007 [doi>10.1145/1273340.1273344]
• 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: 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
• 5: E. Coffman, Z. Liu, and P. Weber. Optimal robot scheduling for web search engines. Journal of Scheduling, (1):15--29, 1998.
• 6: C. S. David R. Karger and J. Wein. Scheduling Algorithms. Algorithms and Theory of Computation Handbook, 1998.
• 7: A. Doan et al. Community information management. IEEE Data Engineering Bulletin, 29(1):64--72, 2006.
• 8: 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]
• 9: Matthias Ehrgott, Multicriteria Optimization, Springer-Verlag New York, Inc., Secaucus, NJ, 2005
• 10: M. Pinedo. Scheduling - Theory, Algorithms, and Systems. Prentice Hall, 1995.
• 11: Vincent T'kindt , Jean-Charles Billaut , H. Scott, Multicriteria Scheduling: Theory, Models and Algorithms, Springer-Verlag New York, Inc., Secaucus, NJ, 2006

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.0 General

General Terms:
Algorithms, Performance, Theory

Keywords:
gardener's problem, multicriteria maintenance scheduling, np-hard, olap, web information monitoring