be.tarsos.lsh

Class Index

java.lang.Object

be.tarsos.lsh.Index

All Implemented Interfaces:

java.io.Serializable

public class Index
extends java.lang.Object
implements java.io.Serializable

The index makes it easy to store vectors and lookup queries efficiently. For the moment the index is stored in memory. It holds a number of hash tables, each with a couple of hashes. Together they can be used for efficient lookup of nearest neighbours.

Author:

Joren Six

See Also:

Serialized Form

Constructor Summary

Constructors

Constructor and Description
Index(HashFamily family, int numberOfHashes, int numberOfHashTables) Create a new index.

Method Summary

Modifier and Type	Method and Description
static Index	deserialize(HashFamily family, int numberOfHashes, int numberOfHashTables) Deserializes the hash table from disk.
int	getNumberOfHashes() The number of hashes used in each hash table in the current index.
int	getNumberOfHashTables() The number of hash tables used in the current index.
int	getTouched() The number of near neighbour candidates that are evaluated during the queries on this index.
void	index(Vector vector) Add a vector to the current index.
java.util.List<Vector>	query(Vector query, int maxSize) Query for the k nearest neighbours in using the current index.
static void	serialize(Index index) Serializes the index to disk.

Methods inherited from class java.lang.Object

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

Constructor Detail

Index

public Index(HashFamily family,
             int numberOfHashes,
             int numberOfHashTables)

Create a new index.

Parameters:

family - The family of hash functions to use.

numberOfHashes - The number of hashes that are concatenated in each hash table. More concatenated hashes means that less candidates are selected for evaluation.

numberOfHashTables - The number of hash tables in use, recall increases with the number of hash tables. Memory use also increases. Time needed to compute a hash also increases marginally.

Method Detail

index

public void index(Vector vector)

Add a vector to the current index. The hashes are calculated with the current hash family and added in the right place.

Parameters:

vector - The vector to add.

getNumberOfHashTables

public int getNumberOfHashTables()

The number of hash tables used in the current index.

Returns:

The number of hash tables used in the current index.

getNumberOfHashes

public int getNumberOfHashes()

The number of hashes used in each hash table in the current index.

Returns:

The number of hashes used in each hash table in the current index.

query

public java.util.List<Vector> query(Vector query,
                                    int maxSize)

Query for the k nearest neighbours in using the current index. The performance (in computing time and recall/precision) depends mainly on how the current index is constructed and how the underlying data looks.

Parameters:

query - The query vector. The center of the neighbourhood.

maxSize - The maximum number of neighbours to return. Beware, the number of neighbours returned lays between zero and the chosen maximum.

Returns:

A list of nearest neighbours, the number of neighbours returned lays between zero and a chosen maximum.

getTouched

public int getTouched()

The number of near neighbour candidates that are evaluated during the queries on this index. Can be used to calculate the average evaluations per query.

Returns:

The number of near neighbour candidates that are evaluated during the queries on this index.

serialize

public static void serialize(Index index)

Serializes the index to disk.

Parameters:

index - the storage object.

deserialize

public static Index deserialize(HashFamily family,
                                int numberOfHashes,
                                int numberOfHashTables)

Deserializes the hash table from disk. If deserialization fails, a new hash table object is created.

Parameters:

family - The family.

numberOfHashes - the number of hashes.

numberOfHashTables - The number of hash tables

Returns:

a new, or deserialized object.