VOLUME Fifty Nine
TITLE: "Data Structures, Near Neighbor Searches, and Methodology: Fifth and Sixth DIMACS Implementation Challenges"
EDITORS: Michael H. Goldwasser, David S. Johnson and Catherine C. McGeoch

Ordering Information

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.

• 1. Preface
• 2. Table of Contents

PREFACE

The DIMACS Implementation Challenges were initiated in 1991 to promote top-quality experimental research on algorithms and data structures. Each Challenge focuses on a particular algorithmic problem area. Participants from around the world undertake year-long coordinated research projects to implement and evaluate promising algorithmic ideas. Each participating group is expected to carry out a common set of core tests for direct comparisons of performance, and also to undertake further experimental research to examine topics such as the effect of implementation variations, or performance on realistic input sets. A workshop held at the end of each Challenge allows participants to present their results and share their new insights about algorithmic performance. Participants are encouraged to submit their codes, instances, and instance generators to an online repository maintained at DIMACS. Those materials can be found at www.dimacs.rutgers.edu/Challenges.

This volume contains reviewed, revised, and expanded versions of papers that were presented at the Fifth and Sixth DIMACS Challenge workshops, held in October 1996 and in January 1999. The volume is divided into three sections. The first contains papers from participants in the Fifth Challenge, which addressed two data structure problems. The second section contains papers from participants in the Sixth Challenge, which focused on problems of near neighbor searches. The third section contains papers from participants in a special "Methodology Day" that was held as part of the Fifth Challenge workshop.

TABLE OF CONTENTS

Foreword                                                v

Preface                                               vii

            Fifth DIMACS Challenge:  Dictionaries
                      and Priority Queues

Partially persistent dynamic sets for history-
  sensitive heuristics 
    R. Battiti                                          1

A practical perfect hashing algorithm
    C. Silverstein                                     23

Computational evaluation of hot queues
    A. V. Goldberg and C. Silverstein                  49

            Sixth DIMACS Challenge: Near Neighbor
                        Searching

Nearest neighbor search for data compression
    K. Zatloukal, M. Holland Johnson, and R. E. Ladner 69

Experimental evaluation of disk-based data structures
  for nearest neighbor searching
    N. Katayama and S. Satoh                           87

Analysis of approximate nearest neighbor searching
  with clustered point sets
    S. Maneewongvatana and D. M. Mount                105

Approximate nearest neighbor search using the
  extended general space-filling curves heuristic
    J. Perez-Cortes and E. Vidal                      125

Locally lifting the curse of dimensionality for
  nearest neighbor search
    P. N. Yianilos                                    177

               Methodology for the Experimental
                    Analysis of Algorithms

The role of experiment in the theory of algorithms
    R. J. Anderson                                    191

Towards a discipline of experimental algorithmics
    B. M. E. Moret                                    197

A theoretician's guide to the experimental analysis
  of algorithms
    D. S. Johnson                                     215

A bibliography of algorithm experimentation
    C. C. McGeoch                                     251

Index of Volumes

DIMACS Homepage