nearoptimal – Near Optimal Locality Sensitive Hashing

class pybrain.supervised.knn.lsh.nearoptimal.MultiDimHash(dim, omega=4, prob=0.80000000000000004)

Class that represents a datastructure that enables nearest neighbours search and methods to do so.

__init__(dim, omega=4, prob=0.80000000000000004)

Create a hash for arrays of dimension dim.

The hyperspace will be split into hypercubes with a sidelength of omega * sqrt(sqrt(dim)), that is omega * radius.

Every point in the dim-dimensional euclidean space will be hashed to its correct bucket with a probability of prob.

insert(point, satellite)

Put a point and its satellite information into the hash structure.

knn(point, k)

Return the k approximate nearest neighbours of the item in the current hash.

Mind that the probabilistic nature of the data structure might not return a nearest neighbor at all and not the nearest neighbour.

See also

Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions

Paper that describes the algorithm used in this module by Alexandr Andoni and Piotr Indyk.