hash

package
v0.0.0-...-5ae0b98 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Mar 10, 2024 License: MIT Imports: 7 Imported by: 0

Documentation

Index

Constants

View Source 
const Prime = 18446744073709551557

largest 64 bit prime

Variables

View Source 
var TableIVa = [16][8]int8{
	{0, 0, 0, 0, 0, 0, 0, 0},
	{4, 0, 0, 0, 0, 0, 0, 0},
	{2, 2, 2, 2, 0, 0, 0, 0},
	{-2, 2, 2, 2, 0, 0, 0, 0},
	{2, 2, 0, 0, 2, 2, 0, 0},
	{-2, 2, 0, 0, 2, 2, 0, 0},
	{2, 2, 0, 0, 0, 0, 2, 2},
	{-2, 2, 0, 0, 0, 0, 2, 2},
	{2, 0, 2, 0, 2, 0, 2, 0},
	{-2, 0, 2, 0, 2, 0, 2, 0},
	{2, 0, 2, 0, 0, 2, 0, 2},
	{-2, 0, 2, 0, 0, 2, 0, 2},
	{2, 0, 0, 2, 2, 0, 0, 2},
	{-2, 0, 0, 2, 2, 0, 0, 2},
	{2, 0, 0, 2, 0, 2, 2, 0},
	{-2, 0, 0, 2, 0, 2, 2, 0},
}

We use table IV instead of table V, it is slower but more understandable

View Source 
var TableIVt = [18][8]int8{
	{0, 0, 0, 0, 0, 0, 0, 0},
	{2, 2, 2, 0, 0, 2, 0, 0},
	{2, 2, 0, 2, 0, 0, 0, 2},
	{2, 0, 2, 2, 0, 0, 2, 0},
	{0, 2, 2, 2, 2, 0, 0, 0},
	{2, 2, 0, 0, 2, 0, 2, 0},
	{2, 0, 2, 0, 2, 0, 0, 2},
	{2, 0, 0, 2, 2, 2, 0, 0},
	{-3, 1, 1, 1, 1, 1, 1, 1},
	{3, -1, -1, 1, 1, -1, 1, 1},
	{3, -1, 1, -1, 1, 1, 1, -1},
	{3, 1, -1, -1, 1, 1, -1, 1},
	{3, 1, 1, 1, 1, -1, -1, -1},
	{3, -1, 1, 1, -1, 1, -1, 1},
	{3, 1, -1, 1, -1, 1, 1, -1},
	{3, 1, 1, -1, -1, -1, 1, 1},
}
View Source 
var TableVi = [256][8]int8{}
View Source 
var TableVii = [4096][3]uint8{}

Functions

func D8Decode 

func D8Decode(f []float64) [8]float64

func DistSquared 

func DistSquared(f1 []float64, f2 []float64) float64

func E8Decode 

func E8Decode(f []float64) ([8]float64, float64)

The E_8 lattice consists of two copies of D_8, offset by the vector (1/2,1/2,1/2,1/2,1/2,1/2,1/2,1/2) See https://en.wikipedia.org/wiki/E8_lattice#Lattice_points for details We follow the algorithm in neilsloane.com/doc/Me83.pdf We first find the closest point in each of the two copies of D_8 Then we return the closer of the two

func FindTableIndex 

func FindTableIndex(v [8]int8) uint8

func GetRandomRotation 

func GetRandomRotation(dim int) []*vec.Vec

func Identity 

func Identity(dim int) []*vec.Vec

Identity matrix

func Is4E8Point 

func Is4E8Point(v [8]int8) bool

Determine if v is a point of the lambda_8 = E_8 * 4 lattice

func LeechLatticeClosest 

func LeechLatticeClosest(f []float64) ([256][3][8]float64, [256][3]float64)

Out lattice is scaled by sqrt8, so we are actually using lambda_8 = E8 * 4 - where all coordinates are multiplied by 4 Thus all lattice points are integers instead of half integers (in fact they are only even integers) This function iterates through the possible arrangements as given in table 6 and stores the closest points to each in p It also stores the (squared) distances to those points in d

func LeechLatticeClosestPoint 

func LeechLatticeClosestPoint(f []float64) ([]float64, float64)

This function iterates through each of the possible arrangements as given in Table 7 And finds the distance given by the arrangement It then returns the closest point and its corresponding distance

func LeechLatticeClosestPoints 

func LeechLatticeClosestPoints(f []float64, numPoints int) ([][]float64, []float64)

This function returns the k closest points and distances instead

func LeechLatticeClosestVector 

func LeechLatticeClosestVector(v *vec.Vec) (*vec.Vec, float64)

func LeechLatticeClosestVectors 

func LeechLatticeClosestVectors(v *vec.Vec, numPoints int) ([]*vec.Vec, []float64)

func Normals 

func Normals(size int) *vec.Vec

Gaussian matrix

func Precompute 

func Precompute()

This function implements the precomputation steps as described in https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=1057135

func RandomRotationMatrix 

func RandomRotationMatrix(dim int) []*vec.Vec

Return a random rotation matrix chosen uniformly

func RandomTranslationVector 

func RandomTranslationVector(dim int, max float64) *vec.Vec

Return a random vector chosen uniformly from the cube

func RandomVector 

func RandomVector(dim int) *vec.Vec

Return a random directional vector

func Sign 

func Sign(v float64) int

Signum, but not 0

func Spans 

func Spans(total int, numSpans int) [][2]int

This function divides the input dimension into copies parts as evenly as possible

Types

type Candidates 

type Candidates struct {
	Indexes   []uint64
	Distances []float64
}

helper to sort points because golang A heap or priority queue would be more efficient

func (*Candidates) Len 

func (c *Candidates) Len() int

func (*Candidates) Less 

func (c *Candidates) Less(i, j int) bool

func (*Candidates) Swap 

func (c *Candidates) Swap(i, j int)

type DistanceSearchQueue 

type DistanceSearchQueue struct {
	// contains filtered or unexported fields
}

func NewDistanceSearchQueue 

func NewDistanceSearchQueue(length int, sources [][]*Element) *DistanceSearchQueue

func (*DistanceSearchQueue) GetBest 

func (d *DistanceSearchQueue) GetBest() []*Element

func (*DistanceSearchQueue) GetNextCandidateToExpand 

func (d *DistanceSearchQueue) GetNextCandidateToExpand() *Element

func (*DistanceSearchQueue) Insert 

func (d *DistanceSearchQueue) Insert(e *Element) bool

func (*DistanceSearchQueue) Len 

func (d *DistanceSearchQueue) Len() int

func (*DistanceSearchQueue) Less 

func (d *DistanceSearchQueue) Less(i, j int) bool

func (*DistanceSearchQueue) Pop 

func (d *DistanceSearchQueue) Pop() interface{}

func (*DistanceSearchQueue) Push 

func (d *DistanceSearchQueue) Push(x interface{})

func (*DistanceSearchQueue) Search 

func (d *DistanceSearchQueue) Search() []*Element

func (*DistanceSearchQueue) Swap 

func (d *DistanceSearchQueue) Swap(i, j int)

type Element 

type Element struct {
	// contains filtered or unexported fields
}

func (*Element) CombineWith 

func (e *Element) CombineWith(e2 *Element)

func (*Element) IncrementCopy 

func (e *Element) IncrementCopy(pos int, sources [][]*Element) *Element

type Hash 

type Hash interface {
	Hash(*vec.Vec) uint64
	// return k hashes (for multiprobing)
	MultiHash(*vec.Vec, int) []uint64
}

Hash is an abstract hash function

type HashCommon 

type HashCommon struct {
	ProjectionLines []*vec.Vec
	Offsets         *vec.Vec
	Orthogonal      bool
	UHash           *UniversalHash
}

func NewHashCommon 

func NewHashCommon(dim, amplification int, max float64, Orthogonal bool) *HashCommon

Rotation and translation and dimension scaling that are common to many LSH hash functions Dimensionality reduction is a random rotation followed by a projection (e.g taking the first k coordinates).

func (*HashCommon) Project 

func (h *HashCommon) Project(v *vec.Vec) *vec.Vec

Apply the rotation and translation

type LatticeHash 

type LatticeHash struct {
	H     *HashCommon
	Scale float64
}

func NewLatticeHash 

func NewLatticeHash(dim int, width, max float64) *LatticeHash

This constructs a new leech lattice hash where the lattice points are the centers of spheres of radius sqrt(8) A random rotation and translation are applied and the space is scaled for the desired "R" - LSH hash width The JL-transform step is performed in the same matrix as rotation

func (*LatticeHash) Hash 

func (l *LatticeHash) Hash(v *vec.Vec) uint64

func (*LatticeHash) HashWithDist 

func (l *LatticeHash) HashWithDist(v *vec.Vec) (*vec.Vec, float64)

This computes the hash and the squared distance to the closest vector

func (*LatticeHash) MultiHash 

func (l *LatticeHash) MultiHash(v *vec.Vec, probes int) []uint64

func (*LatticeHash) MultiProbeHashWithDist 

func (l *LatticeHash) MultiProbeHashWithDist(v *vec.Vec, probes int) ([]*vec.Vec, []float64)

This returns the k closest hashes and squared distances

type MultiLatticeHash 

type MultiLatticeHash struct {
	Hashes      []*LatticeHash
	Permutation []int
	Spans       [][2]int
	UHash       *UniversalHash
}

func NewMultiLatticeHash 

func NewMultiLatticeHash(dim, copies int, width, max float64) *MultiLatticeHash

func (*MultiLatticeHash) Hash 

func (m *MultiLatticeHash) Hash(v *vec.Vec) uint64

func (*MultiLatticeHash) HashWithDist 

func (m *MultiLatticeHash) HashWithDist(v *vec.Vec) (*vec.Vec, float64)

func (*MultiLatticeHash) MultiHash 

func (m *MultiLatticeHash) MultiHash(v *vec.Vec, probes int) []uint64

func (*MultiLatticeHash) MultiProbeHashWithDist 

func (m *MultiLatticeHash) MultiProbeHashWithDist(v *vec.Vec, probes int) ([]*vec.Vec, []float64)

We have to iterate through each of the closest points of the sublattices to find the closest point

type UniversalHash 

type UniversalHash struct {
	Coefficients []*gmp.Int
	Modulus      *gmp.Int
}

func NewUniversalHash 

func NewUniversalHash(dim int) *UniversalHash

func (*UniversalHash) Hash 

func (u *UniversalHash) Hash(v *vec.Vec) uint64

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.