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.
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.
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