Abstract: About this book
This state-of-the-art survey features papers that were selected after an open call following the International Dagstuhl Seminar on Algorithmic Methods for Railway Optimization held in Dagstuhl Castle, Germany, in June 2004. The second part of the volume constitutes the refereed proceedings of the 4th International Workshop on Algorithmic Methods and Models for Optimization of Railways held in Bergen, Norway, in September 2004.
The volume covers algorithmic methods for analyzing and solving problems arising in railway optimizations, with a special focus on the interplay between railway and other public transportation systems. Beside algorithmics and mathematical optimization, the relevance of formal models and the influence of applications on problem modeling are also considered. In addition, the papers address experimental studies and useful prototype implementations.
The 17 full papers presented here were carefully reviewed and selected from numerous submissions and are organized into topical sections covering network and line planning, timetabling and timetable information, rolling stock and crew scheduling, and real-time operations.
Abstract: Counting items in a distributed system, and estimating the cardinality of multisets in particular,
is important for a large variety of applications and a fundamental building block for emerging Internet-scale information systems. Examples of such applications range from optimizing query access plans in peer-to-peer data sharing, to computing the significance (rank/score) of data items in distributed information retrieval. The general formal problem addressed in this article is computing the network-wide distinct number of items with some property (e.g., distinct files with file name
containing “spiderman”) where each node in the network holds an arbitrary subset, possibly overlapping the subsets of other nodes. The key requirements that a viable approach must satisfy are:
(1) scalability towards very large network size, (2) efficiency regarding messaging overhead, (3) load
balance of storage and access, (4) accuracy of the cardinality estimation, and (5) simplicity and easy
integration in applications. This article contributes the DHS (Distributed Hash Sketches) method
for this problem setting: a distributed, scalable, efficient, and accurate multiset cardinality estimator.
DHSis based on hash sketches for probabilistic counting, but distributes the bits of each counter
across network nodes in a judicious manner based on principles of Distributed Hash Tables, paying
careful attention to fast access and aggregation as well as update costs. The article discusses various
design choices, exhibiting tunable trade-offs between estimation accuracy, hop-count efficiency, and
load distribution fairness. We further contribute a full-fledged, publicly available, open-source implementation of all our methods, and a comprehensive experimental evaluation for various settings.