DIMACS Series in
Discrete Mathematics and Theoretical Computer Science

VOLUME Fifty
TITLE: "External Memory Algorithms"
EDITOR: James M. Abello

Ordering Information

This volume may be obtained from the AMS or through bookstores in your area.

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.

PREFACE

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.

TABLE OF CONTENTS


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 Index of Volumes
DIMACS Homepage
Contacting the Center
Document last modified on February 8, 2000.