smile.neighbor

Class SNLSH<E>

java.lang.Object

smile.neighbor.SNLSH<E>

All Implemented Interfaces:

KNNSearch<SNLSH.AbstractSentence,E>, NearestNeighborSearch<SNLSH.AbstractSentence,E>, RNNSearch<SNLSH.AbstractSentence,E>

public class SNLSH<E>
extends java.lang.Object
implements NearestNeighborSearch<SNLSH.AbstractSentence,E>, KNNSearch<SNLSH.AbstractSentence,E>, RNNSearch<SNLSH.AbstractSentence,E>

Locality-Sensitive Hashing for Signatures. LSH is an efficient algorithm for approximate nearest neighbor search in high dimensional spaces by performing probabilistic dimension reduction of data. The basic idea is to hash the input items so that similar items are mapped to the same buckets with high probability (the number of buckets being much smaller than the universe of possible input items). To avoid computing the similarity of every pair of sets or their signatures. If we are given signatures for the sets, we may divide them into bands, and only measure the similarity of a pair of sets if they are identical in at least one band. By choosing the size of bands appropriately, we can eliminate from consideration most of the pairs that do not meet our threshold of similarity.

By default, the query object (reference equality) is excluded from the neighborhood. You may change this behavior with setIdenticalExcluded. Note that you may observe weird behavior with String objects. JVM will pool the string literal objects. So the below variables String a = "ABC"; String b = "ABC"; String c = "AB" + "C"; are actually equal in reference test a == b == c. With toy data that you type explicitly in the code, this will cause problems. Fortunately, the data would be read from secondary storage in production.

References

1. Moses S. Charikar. Similarity Estimation Techniques from Rounding Algorithms

See Also:

LSH

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	SNLSH.AbstractSentence

Constructor Summary

Constructors

Constructor and Description
SNLSH(int bandSize)

Method Summary

Modifier and Type	Method and Description
Neighbor<SNLSH.AbstractSentence,E>[]	knn(SNLSH.AbstractSentence q, int k) Search the k nearest neighbors to the query.
Neighbor<SNLSH.AbstractSentence,E>	nearest(SNLSH.AbstractSentence q) Search the nearest neighbor to the given sample.
void	put(SNLSH.AbstractSentence sentence, E v)
void	range(SNLSH.AbstractSentence q, double radius, java.util.List<Neighbor<SNLSH.AbstractSentence,E>> neighbors) Search the neighbors in the given radius of query object, i.e.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

SNLSH

public SNLSH(int bandSize)

Method Detail

put

public void put(SNLSH.AbstractSentence sentence,
                E v)

knn

public Neighbor<SNLSH.AbstractSentence,E>[] knn(SNLSH.AbstractSentence q,
                                                int k)

Description copied from interface: KNNSearch

Search the k nearest neighbors to the query.

Specified by:

knn in interface KNNSearch<SNLSH.AbstractSentence,E>

Parameters:

q - the query key.

k - the number of nearest neighbors to search for.

nearest

public Neighbor<SNLSH.AbstractSentence,E> nearest(SNLSH.AbstractSentence q)

Description copied from interface: NearestNeighborSearch

Search the nearest neighbor to the given sample.

Specified by:

nearest in interface NearestNeighborSearch<SNLSH.AbstractSentence,E>

Parameters:

q - the query key.

Returns:

the nearest neighbor

range

public void range(SNLSH.AbstractSentence q,
                  double radius,
                  java.util.List<Neighbor<SNLSH.AbstractSentence,E>> neighbors)

Description copied from interface: RNNSearch

Search the neighbors in the given radius of query object, i.e. d(q, v) ≤ radius.

Specified by:

range in interface RNNSearch<SNLSH.AbstractSentence,E>

Parameters:

q - the query key.

radius - the radius of search range from target.

neighbors - the list to store found neighbors in the given range on output.