Available Software

**Search Algorithm**( gzip'd tarfile)- algorithm.h
- algorithm.c (<-- this will be replaced by you)
- client.h
- client.c
- messages.h
- oracle.h
- search.c (<-- you may want to modify this too)
- Makefile

**Data Set Oracle**( gzip'd tarfile)- euclid.c (<-- this will be replaced by you)
- messages.h
- oracle.h
- server.h
- server.c
- Makefile

**Brute Force****Contributor:**Michael Goldwasser, wass@cs.princeton.edu**Language:**C**Available as:**[ gzip'd tarfile (6K) ]**Description:**This algorithm is a brilliant one, using almost no space, no preprocessing, and using only linear time to answer queries.**SR-Tree****Contributor:**Norio Katayama, katayama@rd.nacsis.ac.jp**Version:**1.0 (August 31 1998)**Language:**C or C++**Available as:**[ gzip'd tarfile (184K) ]**Description:**Click here for information about these participants and the algorithm.**ANN**(includes kd-tree implementations)**Contributor:**David Mount, mount@cs.umd.edu**Language:**C++**ANN Home Page:**http://www.cs.umd.edu/~mount/ANN/**Description:**ANN is a library written in the C++ programming language to support both exact and approximate nearest neighbor searching in Euclidean spaces of various dimensions. In particular, ANN implements kd-trees with a choice of several possible splitting rules, as well as other box-decomposition trees.To download ANN along with documentation on using the library, please see the ANN home page.

In addition, if you would like a wrapper around ANN which makes in conform to the "official" Implementation Challenge development standards, you may download the additional package: [ gzip'd tarfile (6K) ]

**Euclid****Contributor:**Michael Goldwasser, wass@cs.princeton.edu**Version:**1.0 (August 24 1998)**Language:**C**Available as:**[ gzip'd tarfile (6K) ]**Description:**This program provides an example of an oracle for a Euclidean metric space. The points can be either read from a file or generated uniformly at random from the unit hypercube. Additionally, points can be color-coded for classification (optionally). The distance metric can be set to the L_p norm for any positive integer p, or to the L_infinity norm. (This oracle combines and replaces the previous "randcube" and "color_euclid" oracles)**Text - Edit Distance****Contributor:**Michael Goldwasser, wass@cs.princeton.edu (Based on original code provided by Sergey Brin)**Version:**1.0 (January 16 1998)**Language:**C**Available as:**[ gzip'd tarfile (6K) ]**Description:**This program provides an example of two distance metrics creating a space over lines of text provided at runtime. The space can be created using one of two edit distance functions as the metric.**Gauss****Contributor:**Alfons Juan, ajuan@iti.upv.es**Version:**1.0 (May 1998)**Language:**C**Available as:**[ gzip'd tarfile (13K) ]**Description:**gaussora (GAUSSian ORAcle) is an oracle for Euclidean samples generated from a mixture of Gaussian distributions. Additionally, generated samples are color-coded based on the individual distribution responsible for each sample.**Hidden Markov Model****Contributor:**Alfons Juan, ajuan@iti.upv.es**Version:**1.2 (July 9 1998)**Language:**C**Available as:**[ gzip'd tarfile (204K) ]**Description:**hmmora (Hidden Markov Model ORAcle) is an oracle for string samples generated from a mixture of Hidden Markov Models. Additionally, generated samples are color-coded based on the individual distribution responsible for each sample.**Image Vectors****Contributor:**Norio Katayama, katayama@rd.nacsis.ac.jp**Available as:**[ gzip'd ascii (3.2M) ]**Description:**A file of 40700 Euclidean vectors in 20-dimensional space, generated as feature vectors from images downloaded from NASA. As an experiment, 37000 of these vectors are randomly selected to be in the original data set, with the remaining 3700 used as query points. Click here for more information about the generation of the vectors. The file is formatted for use as input to the Euclid oracle.

Sixth DIMACS Implementation Challenge.

Previous DIMACS Implementation Challenges.

Maintained by Michael Goldwasser

challenge6@dimacs.rutgers.edu

Document last modified on May 26, 1999.