Scheduling of Data Transcription in Periodically Connected Databases

Abstract

Contemporary data management in applications such as pervasive systems, Web‐based supply chain management, data warehouses, and Web crawlers involve the periodic transcription of data onto secondary devices in a networked environment. In this paper, we focus on the scheduling of periodic data transcription in append‐only environments, such as e‐mail inboxes, newsgroups, technical support bulletin boards, or procurement requests. If the client connects to the server too frequently, the client will nearly always have up‐to‐date information, but the usage of network resources may be excessive. Conversely, very infrequent connections will conserve network resources, but the client's data may often be significantly out of date, which may also be costly (in terms of lost opportunities, for example). Thus, the best transcription policies should make on optimal trade‐off between these costs. Our approach to evaluating this trade‐off is to use modeling techniques from the field of stochastic processes. The paper presents a general model for data insertions on the server side, using compound nonhomogeneous Poisson processes, and compares several transcription policies in terms of both transcription cost and obsolescence cost. The comparisons use a validation data set from a real data feed, and our models were calibrated using a separate training set from the same feed. We find that transcription policies based on a nonhomogeneous Poisson arrival model often outperform simpler policies.

Keywords:

• Poisson models
• Information systems applications

Acknowledgments

We would like to thank Ben Melamed, Bob Vanderbei, and Themistoklis Palpanas for their help. Also, the assistance of Louiqa Raschid and Laura Bright with the analysis of the World Cup data is highly appreciated.

Zachary G. Stoumbos' work was funded in part by the Law School Admission Council (LSAC) and by a 2001 Rutgers Faculty of Management Research Fellowship. The opinions and conclusions contained in this publication are those of the authors and do not necessarily reflect the position or policy of LSAC.

Notes

^a http://www.microsoft.com/servers/miserver/.

^b http://www.comalex.com/central.htm.

^cWhile newsgroups are periodically truncated for space reasons, we assume the clients connect frequently enough to be able to review all newly‐arrived messages before they are deleted.

^dOrthogonal research efforts involve probabilistic database systems (e.g., Ref.[6]), yet probabilistic databases are concerned with uncertainty in the stored data, rather than data evolution.

^eThe data was taken from http://ita.ee.lbl.gov/html/contrib/WorldCup.html.

Additional information

Notes on contributors

Avigdor Gal

Currently on leave from Rutgers, serving as a Senior Lecturer at the Technion, Israel Institute of Technology.