Data Structures, Near Neighbor Searches, and Methodology

by Goldwasser, Michael H.; McGeoch, Catherine C.

• ISBN13: 9780821828922
• ISBN10: 0821828924
• Format: Hardcover
• Copyright: 2002-12-01
• Publisher: Amer Mathematical Society

Summary

This book presents reviewed and revised papers from the fifth and sixth DIMACS Implementation Challenge workshops. These workshops, held approximately annually, aim at encouraging high-quality work in experimental analysis of data structures and algorithms. The papers published in this volume are the results of year-long coordinated research projects and contain new findings and insights. Three papers address the performance evaluation of implementations for two fundamental data structures, dictionaries and priority queues as used in the context of real applications. Another four papers consider the still evolving topic of methodologies for experimental algorithmics. Five papers are concerned with implementations of algorithms for nearest neighbor search in high dimensional spaces, an area with applications in information retrieval and data mining on collections of Web documents, DNA sequences, images and various other data types.

Table of Contents

Partially persistent dynamic sets for history-sensitive heuristics

A practical perfect hashing algorithm

Computational evaluation of hot queues

Nearest neighbor search for data compression

Experimental evaluation of disk-based data structures for nearest neighbor searching

Analysis of approximate nearest neighbor searching with clustered point sets

Approximate nearest neighbor search using the extended general space-filling curves heuristic

Locally lifting the curse of dimensionality for nearest neighbor search

The role of experiment in the theory of algorithms

Towards a discipline of experimental algorithmics

A theoretician's guide to the experimental analysis of algorithms

A bibliography of algorithm experimentation

Table of Contents provided by Publisher. All Rights Reserved.