Discrete Mathematics and Theoretical Computer Science

TITLE: "External Memory Algorithms"

EDITOR: James M. Abello

To order through AMS contact the AMS Customer Services Department, P.O. Box 6248, Providence, Rhode Island 02940-6248 USA. For Visa, Mastercard, Discover, and American Express orders call 1-800-321-4AMS.

You may also visit the
AMS Bookstore and
order directly from there.
DIMACS ** does not** distribute or sell these books.

Techniques from computer science and mathematics are used to solve combinatorial problems in designing memory algorithms when associated data require a hierarchy of storage devices. These solutions employ "extended memory algorithms". The input/output (I/O) communication between the levels of the hierarchy is often a significant bottleneck in applications that process massive amounts of data. Gains in performance may be possible by incorporating locality directly into the algorithms and managing the contents of each storage level.

The relative difference in data access speeds is most apparent between random access memory and magnetic disks. Therefore, much research has been devoted to algorithms that focus on the I/O bottleneck. These algorithms are usually called "external memory", "out-of-core", or "I/O algorithms".

This volume presents new research results and current techniques for the design and analysis of external memory algorithms. The articles grew out of the workshop, "External Memory Algorithms and Visualization" held at DIMACS. Leading researchers were invited to give lectures and to contribute their work. Topics presented include problems in computational geometry, graph theory, data compression, disk scheduling, linear algebra, statistics, software libraries, text and string processing, visualization, wavelets, and industrial applications.

The vitality of the research and the interdisciplinary nature of the event produced fruitful ground for the compelling fusion of ideas and methods. This volume comprises the rich results that grew out of that process.

Forword ix Preface xi External memory algorithms and data structures J. S. Vitter 1 Synopsis data structures for massive data sets P. B. Gibbons and Y. Matias 39 Calculating robust depth measures for large data sets I. Al-Furaih, T. Johnson, and S. Ranka 71 Efficient cross-trees for external memory R. Grossi and G. F. Italiano 87 Computing on data streams M. R. Henzinger, P. Raghavan, and S. Rajagopalan 107 On maximum clique problems in very large graphs J. Abello, P. M. Pardalos, and M. G. C. Resende 119 I/O-optimal computation of segment intersections A. Crauser, P. Ferragina, K. Mehlhorn, U. Meyer, and E. A. Ramos 131 On showing lower bounds for external-memory computational geometry problems L. Arge and P. B. Miltersen 139 A survey of out-of-core algorithms in numerical linear algebra S. Toledo 161 Concrete software libraries K.-P. Vo 181 S(b)-tree library: An efficient way of indexing data K. V. Shvachko 207 ASP: Adaptive online parallel disk scheduling M. Kallahalla and P. J. Varman 223 Efficient schemes for distributing data on parallel memory systems S. K. Das and M. C. Pinotti 233 External memory techniques for isosurface extraction in scientific visualization Y.-J. Chiang and C. T. Silva 247 R-tree retrieval of unstructured volume data for visualization S. T. Leutenegger and K.-L. Ma 279 Author Index 293 Subject Index 295

Index of Volumes

DIMACS Homepage

Contacting the Center

Document last modified on February 8, 2000.