jbergner
94dbd4ccab
All checks were successful
release-tag / release-image (push) Successful in 2m32s
797 lines
21 KiB
Go
797 lines
21 KiB
Go
package vectorgraph
|
|
|
|
import (
|
|
"container/heap"
|
|
"math"
|
|
"math/bits"
|
|
"sort"
|
|
"sync"
|
|
)
|
|
|
|
// Entry is the complete input required by the deterministic vector graph.
|
|
// The package deliberately has no model, network or LLM dependency so the
|
|
// calculation can be moved to another process later as long as embeddings are
|
|
// supplied with the job.
|
|
type Entry struct {
|
|
ID string
|
|
Vector []float32
|
|
}
|
|
|
|
type Config struct {
|
|
// Workers parallelizes the independent per-node candidate/exact-cosine phase.
|
|
// Zero keeps the conservative single-worker behavior. Results remain
|
|
// deterministic because workers write per-index slots and aggregation happens
|
|
// in sorted node order after all workers complete.
|
|
Workers int
|
|
Neighbors int
|
|
CandidateLimit int
|
|
HashBits int
|
|
HashTables int
|
|
BandBits int
|
|
MinSimilarity float64
|
|
MinAffinity float64
|
|
StrongSimilarity float64
|
|
Layout bool
|
|
Smoothing float64
|
|
}
|
|
|
|
type Link struct {
|
|
Source string
|
|
Target string
|
|
Similarity float64
|
|
Affinity float64
|
|
Confidence float64
|
|
SourceRank int
|
|
TargetRank int
|
|
Reciprocal bool
|
|
}
|
|
|
|
type Position struct {
|
|
ID string
|
|
X float64
|
|
Y float64
|
|
Z float64
|
|
}
|
|
|
|
type Stats struct {
|
|
Indexed int
|
|
Focused int
|
|
BucketLookups int
|
|
CandidatePairs int
|
|
ExactComparisons int
|
|
Links int
|
|
ReciprocalLinks int
|
|
}
|
|
|
|
type Result struct {
|
|
Links []Link
|
|
Positions []Position
|
|
Stats Stats
|
|
}
|
|
|
|
type indexedEntry struct {
|
|
Entry
|
|
signatures []uint64
|
|
}
|
|
|
|
type coarseCandidate struct {
|
|
index int
|
|
distance int
|
|
}
|
|
|
|
type coarseMaxHeap []coarseCandidate
|
|
|
|
func (h coarseMaxHeap) Len() int { return len(h) }
|
|
func (h coarseMaxHeap) Less(i, j int) bool {
|
|
if h[i].distance == h[j].distance {
|
|
return h[i].index > h[j].index
|
|
}
|
|
return h[i].distance > h[j].distance
|
|
}
|
|
func (h coarseMaxHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
|
|
func (h *coarseMaxHeap) Push(x any) { *h = append(*h, x.(coarseCandidate)) }
|
|
func (h *coarseMaxHeap) Pop() any {
|
|
old := *h
|
|
n := len(old)
|
|
x := old[n-1]
|
|
*h = old[:n-1]
|
|
return x
|
|
}
|
|
|
|
type neighbor struct {
|
|
index int
|
|
similarity float64
|
|
}
|
|
|
|
func normalizeConfig(cfg Config) Config {
|
|
if cfg.Workers < 1 {
|
|
cfg.Workers = 1
|
|
}
|
|
if cfg.Workers > 256 {
|
|
cfg.Workers = 256
|
|
}
|
|
if cfg.Neighbors < 1 {
|
|
cfg.Neighbors = 4
|
|
}
|
|
if cfg.Neighbors > 16 {
|
|
cfg.Neighbors = 16
|
|
}
|
|
if cfg.CandidateLimit < cfg.Neighbors*4 {
|
|
cfg.CandidateLimit = cfg.Neighbors * 4
|
|
}
|
|
if cfg.CandidateLimit < 32 {
|
|
cfg.CandidateLimit = 32
|
|
}
|
|
if cfg.CandidateLimit > 512 {
|
|
cfg.CandidateLimit = 512
|
|
}
|
|
if cfg.HashBits < 8 {
|
|
cfg.HashBits = 24
|
|
}
|
|
if cfg.HashBits > 63 {
|
|
cfg.HashBits = 63
|
|
}
|
|
if cfg.HashTables < 1 {
|
|
cfg.HashTables = 2
|
|
}
|
|
if cfg.HashTables > 4 {
|
|
cfg.HashTables = 4
|
|
}
|
|
if cfg.BandBits < 4 || cfg.BandBits > cfg.HashBits || cfg.HashBits%cfg.BandBits != 0 {
|
|
cfg.BandBits = 8
|
|
}
|
|
if cfg.HashBits%cfg.BandBits != 0 {
|
|
cfg.BandBits = cfg.HashBits
|
|
}
|
|
if cfg.MinSimilarity <= 0 {
|
|
cfg.MinSimilarity = .80
|
|
}
|
|
if cfg.MinSimilarity > 1 {
|
|
cfg.MinSimilarity = 1
|
|
}
|
|
if cfg.MinAffinity <= 0 {
|
|
cfg.MinAffinity = .35
|
|
}
|
|
if cfg.MinAffinity > 1 {
|
|
cfg.MinAffinity = 1
|
|
}
|
|
if cfg.StrongSimilarity <= 0 {
|
|
cfg.StrongSimilarity = math.Max(.92, cfg.MinSimilarity+.08)
|
|
}
|
|
if cfg.StrongSimilarity > 1 {
|
|
cfg.StrongSimilarity = 1
|
|
}
|
|
if cfg.Smoothing < 0 {
|
|
cfg.Smoothing = 0
|
|
}
|
|
if cfg.Smoothing > .75 {
|
|
cfg.Smoothing = .75
|
|
}
|
|
if cfg.Layout && cfg.Smoothing == 0 {
|
|
cfg.Smoothing = .22
|
|
}
|
|
return cfg
|
|
}
|
|
|
|
// Build constructs a sparse semantic-neighbour graph using only arithmetic on
|
|
// already existing embeddings. Candidate generation uses deterministic sparse
|
|
// random-projection LSH; exact Cosine is calculated only for a bounded
|
|
// shortlist. Edges use mutual-kNN/local-scaling semantics instead of claiming
|
|
// that vector proximity alone proves a factual same_topic relation.
|
|
func Build(entries []Entry, cfg Config) Result {
|
|
cfg = normalizeConfig(cfg)
|
|
indexed := make([]indexedEntry, 0, len(entries))
|
|
dimension := 0
|
|
for _, entry := range entries {
|
|
if entry.ID == "" || len(entry.Vector) == 0 {
|
|
continue
|
|
}
|
|
if dimension == 0 {
|
|
dimension = len(entry.Vector)
|
|
}
|
|
if len(entry.Vector) != dimension {
|
|
continue
|
|
}
|
|
cp := append([]float32(nil), entry.Vector...)
|
|
indexed = append(indexed, indexedEntry{Entry: Entry{ID: entry.ID, Vector: cp}})
|
|
}
|
|
sort.Slice(indexed, func(i, j int) bool { return indexed[i].ID < indexed[j].ID })
|
|
result := Result{}
|
|
result.Stats.Indexed = len(indexed)
|
|
result.Stats.Focused = len(indexed)
|
|
if len(indexed) < 2 {
|
|
return result
|
|
}
|
|
|
|
for i := range indexed {
|
|
indexed[i].signatures = signaturesFor(indexed[i].Vector, cfg.HashBits, cfg.HashTables)
|
|
}
|
|
bands := cfg.HashBits / cfg.BandBits
|
|
bandMask := uint64(1<<cfg.BandBits) - 1
|
|
buckets := make(map[uint64][]int, len(indexed)*cfg.HashTables*bands/2)
|
|
for i := range indexed {
|
|
for table := 0; table < cfg.HashTables; table++ {
|
|
sig := indexed[i].signatures[table]
|
|
for band := 0; band < bands; band++ {
|
|
value := (sig >> (band * cfg.BandBits)) & bandMask
|
|
key := bucketKey(table, band, value)
|
|
buckets[key] = append(buckets[key], i)
|
|
}
|
|
}
|
|
}
|
|
|
|
nearest := make([][]neighbor, len(indexed))
|
|
sigmas := make([]float64, len(indexed))
|
|
perNodeStats := make([]Stats, len(indexed))
|
|
parallelIndices(len(indexed), cfg.Workers, func(jobs <-chan int) {
|
|
seen := make([]int, len(indexed))
|
|
generation := 1
|
|
for i := range jobs {
|
|
h := &coarseMaxHeap{}
|
|
heap.Init(h)
|
|
candidateCount := 0
|
|
generation++
|
|
st := &perNodeStats[i]
|
|
for table := 0; table < cfg.HashTables; table++ {
|
|
sig := indexed[i].signatures[table]
|
|
for band := 0; band < bands; band++ {
|
|
value := (sig >> (band * cfg.BandBits)) & bandMask
|
|
st.BucketLookups++
|
|
for _, j := range buckets[bucketKey(table, band, value)] {
|
|
if j == i || seen[j] == generation {
|
|
continue
|
|
}
|
|
seen[j] = generation
|
|
candidateCount++
|
|
pushCoarse(h, coarseCandidate{index: j, distance: signatureDistance(indexed[i].signatures, indexed[j].signatures)}, cfg.CandidateLimit)
|
|
}
|
|
}
|
|
}
|
|
// Sparse/outlier signatures should still get a bounded chance to link.
|
|
// The fallback is deterministic and only scans hashes, never embeddings.
|
|
if h.Len() < cfg.Neighbors {
|
|
for j := range indexed {
|
|
if j == i || seen[j] == generation {
|
|
continue
|
|
}
|
|
pushCoarse(h, coarseCandidate{index: j, distance: signatureDistance(indexed[i].signatures, indexed[j].signatures)}, cfg.CandidateLimit)
|
|
}
|
|
}
|
|
st.CandidatePairs = candidateCount
|
|
coarse := make([]coarseCandidate, h.Len())
|
|
for k := len(coarse) - 1; k >= 0; k-- {
|
|
coarse[k] = heap.Pop(h).(coarseCandidate)
|
|
}
|
|
exact := make([]neighbor, 0, len(coarse))
|
|
for _, candidate := range coarse {
|
|
sim := cosine(indexed[i].Vector, indexed[candidate.index].Vector)
|
|
st.ExactComparisons++
|
|
exact = append(exact, neighbor{index: candidate.index, similarity: sim})
|
|
}
|
|
sort.Slice(exact, func(a, b int) bool {
|
|
if exact[a].similarity == exact[b].similarity {
|
|
return indexed[exact[a].index].ID < indexed[exact[b].index].ID
|
|
}
|
|
return exact[a].similarity > exact[b].similarity
|
|
})
|
|
if len(exact) > cfg.Neighbors {
|
|
exact = exact[:cfg.Neighbors]
|
|
}
|
|
nearest[i] = exact
|
|
if len(exact) > 0 {
|
|
kth := exact[len(exact)-1].similarity
|
|
sigmas[i] = math.Max(1e-4, 1-kth)
|
|
} else {
|
|
sigmas[i] = 1
|
|
}
|
|
}
|
|
})
|
|
for i := range perNodeStats {
|
|
result.Stats.BucketLookups += perNodeStats[i].BucketLookups
|
|
result.Stats.CandidatePairs += perNodeStats[i].CandidatePairs
|
|
result.Stats.ExactComparisons += perNodeStats[i].ExactComparisons
|
|
}
|
|
|
|
rankMaps := make([]map[int]int, len(indexed))
|
|
for i, list := range nearest {
|
|
m := make(map[int]int, len(list))
|
|
for rank, n := range list {
|
|
m[n.index] = rank + 1
|
|
}
|
|
rankMaps[i] = m
|
|
}
|
|
pairSeen := map[[2]int]bool{}
|
|
adjacency := make([][]struct {
|
|
j int
|
|
w float64
|
|
}, len(indexed))
|
|
for i, list := range nearest {
|
|
for rank, n := range list {
|
|
j := n.index
|
|
pair := [2]int{i, j}
|
|
if i > j {
|
|
pair = [2]int{j, i}
|
|
}
|
|
if pairSeen[pair] {
|
|
continue
|
|
}
|
|
pairSeen[pair] = true
|
|
targetRank := rankMaps[j][i]
|
|
reciprocal := targetRank > 0
|
|
sim := n.similarity
|
|
if otherRank := targetRank; otherRank > 0 {
|
|
sim = math.Max(sim, nearest[j][otherRank-1].similarity)
|
|
}
|
|
if sim < cfg.MinSimilarity {
|
|
continue
|
|
}
|
|
distance := math.Max(1e-6, 1-sim)
|
|
affinity := math.Exp(-(distance * distance) / (sigmas[i] * sigmas[j]))
|
|
if !reciprocal && sim < cfg.StrongSimilarity {
|
|
continue
|
|
}
|
|
if reciprocal && affinity < cfg.MinAffinity {
|
|
continue
|
|
}
|
|
confidence := clamp01(.55*sim + .45*affinity)
|
|
sourceRank, finalTargetRank := rank+1, targetRank
|
|
if i > j {
|
|
sourceRank, finalTargetRank = targetRank, rank+1
|
|
}
|
|
link := Link{Source: indexed[pair[0]].ID, Target: indexed[pair[1]].ID, Similarity: sim, Affinity: affinity, Confidence: confidence, SourceRank: sourceRank, TargetRank: finalTargetRank, Reciprocal: reciprocal}
|
|
result.Links = append(result.Links, link)
|
|
result.Stats.Links++
|
|
if reciprocal {
|
|
result.Stats.ReciprocalLinks++
|
|
}
|
|
w := math.Max(.05, affinity)
|
|
adjacency[pair[0]] = append(adjacency[pair[0]], struct {
|
|
j int
|
|
w float64
|
|
}{pair[1], w})
|
|
adjacency[pair[1]] = append(adjacency[pair[1]], struct {
|
|
j int
|
|
w float64
|
|
}{pair[0], w})
|
|
}
|
|
}
|
|
sort.Slice(result.Links, func(i, j int) bool {
|
|
if result.Links[i].Source == result.Links[j].Source {
|
|
return result.Links[i].Target < result.Links[j].Target
|
|
}
|
|
return result.Links[i].Source < result.Links[j].Source
|
|
})
|
|
|
|
if cfg.Layout {
|
|
result.Positions = semanticPositions(indexed, adjacency, cfg.Smoothing)
|
|
}
|
|
return result
|
|
}
|
|
|
|
// BuildFocused runs a conservative second-pass nearest-neighbour search for a
|
|
// bounded subset of entries while keeping the complete vector corpus available
|
|
// as the candidate pool. It is intended for orphan recovery after the primary
|
|
// mutual-kNN pass. Unlike Build, it does not claim reciprocity because target
|
|
// neighbourhoods outside the focus set are deliberately not recomputed. A
|
|
// focused link therefore has to pass both the cosine and one-sided local
|
|
// affinity gates. The function is deterministic and performs no model or
|
|
// network call.
|
|
func BuildFocused(entries []Entry, focusIDs map[string]bool, cfg Config) Result {
|
|
cfg = normalizeConfig(cfg)
|
|
indexed := make([]indexedEntry, 0, len(entries))
|
|
dimension := 0
|
|
for _, entry := range entries {
|
|
if entry.ID == "" || len(entry.Vector) == 0 {
|
|
continue
|
|
}
|
|
if dimension == 0 {
|
|
dimension = len(entry.Vector)
|
|
}
|
|
if len(entry.Vector) != dimension {
|
|
continue
|
|
}
|
|
cp := append([]float32(nil), entry.Vector...)
|
|
indexed = append(indexed, indexedEntry{Entry: Entry{ID: entry.ID, Vector: cp}})
|
|
}
|
|
sort.Slice(indexed, func(i, j int) bool { return indexed[i].ID < indexed[j].ID })
|
|
result := Result{}
|
|
result.Stats.Indexed = len(indexed)
|
|
if len(indexed) < 2 || len(focusIDs) == 0 {
|
|
return result
|
|
}
|
|
|
|
focus := make([]bool, len(indexed))
|
|
for i := range indexed {
|
|
if focusIDs[indexed[i].ID] {
|
|
focus[i] = true
|
|
result.Stats.Focused++
|
|
}
|
|
indexed[i].signatures = signaturesFor(indexed[i].Vector, cfg.HashBits, cfg.HashTables)
|
|
}
|
|
if result.Stats.Focused == 0 {
|
|
return result
|
|
}
|
|
|
|
bands := cfg.HashBits / cfg.BandBits
|
|
bandMask := uint64(1<<cfg.BandBits) - 1
|
|
buckets := make(map[uint64][]int, len(indexed)*cfg.HashTables*bands/2)
|
|
for i := range indexed {
|
|
for table := 0; table < cfg.HashTables; table++ {
|
|
sig := indexed[i].signatures[table]
|
|
for band := 0; band < bands; band++ {
|
|
value := (sig >> (band * cfg.BandBits)) & bandMask
|
|
buckets[bucketKey(table, band, value)] = append(buckets[bucketKey(table, band, value)], i)
|
|
}
|
|
}
|
|
}
|
|
|
|
perNodeStats := make([]Stats, len(indexed))
|
|
perNodeLinks := make([][]Link, len(indexed))
|
|
parallelIndices(len(indexed), cfg.Workers, func(jobs <-chan int) {
|
|
seen := make([]int, len(indexed))
|
|
generation := 1
|
|
for i := range jobs {
|
|
if !focus[i] {
|
|
continue
|
|
}
|
|
h := &coarseMaxHeap{}
|
|
heap.Init(h)
|
|
candidateCount := 0
|
|
generation++
|
|
st := &perNodeStats[i]
|
|
for table := 0; table < cfg.HashTables; table++ {
|
|
sig := indexed[i].signatures[table]
|
|
for band := 0; band < bands; band++ {
|
|
value := (sig >> (band * cfg.BandBits)) & bandMask
|
|
st.BucketLookups++
|
|
for _, j := range buckets[bucketKey(table, band, value)] {
|
|
if j == i || seen[j] == generation {
|
|
continue
|
|
}
|
|
seen[j] = generation
|
|
candidateCount++
|
|
pushCoarse(h, coarseCandidate{index: j, distance: signatureDistance(indexed[i].signatures, indexed[j].signatures)}, cfg.CandidateLimit)
|
|
}
|
|
}
|
|
}
|
|
if h.Len() < cfg.Neighbors {
|
|
for j := range indexed {
|
|
if j == i || seen[j] == generation {
|
|
continue
|
|
}
|
|
pushCoarse(h, coarseCandidate{index: j, distance: signatureDistance(indexed[i].signatures, indexed[j].signatures)}, cfg.CandidateLimit)
|
|
}
|
|
}
|
|
st.CandidatePairs = candidateCount
|
|
coarse := make([]coarseCandidate, h.Len())
|
|
for k := len(coarse) - 1; k >= 0; k-- {
|
|
coarse[k] = heap.Pop(h).(coarseCandidate)
|
|
}
|
|
exact := make([]neighbor, 0, len(coarse))
|
|
for _, candidate := range coarse {
|
|
sim := cosine(indexed[i].Vector, indexed[candidate.index].Vector)
|
|
st.ExactComparisons++
|
|
exact = append(exact, neighbor{index: candidate.index, similarity: sim})
|
|
}
|
|
sort.Slice(exact, func(a, b int) bool {
|
|
if exact[a].similarity == exact[b].similarity {
|
|
return indexed[exact[a].index].ID < indexed[exact[b].index].ID
|
|
}
|
|
return exact[a].similarity > exact[b].similarity
|
|
})
|
|
if len(exact) > cfg.Neighbors {
|
|
exact = exact[:cfg.Neighbors]
|
|
}
|
|
if len(exact) == 0 {
|
|
continue
|
|
}
|
|
sigma := math.Max(1e-4, 1-exact[len(exact)-1].similarity)
|
|
links := make([]Link, 0, len(exact))
|
|
for rank, n := range exact {
|
|
if n.similarity < cfg.MinSimilarity {
|
|
continue
|
|
}
|
|
distance := math.Max(1e-6, 1-n.similarity)
|
|
affinity := math.Exp(-(distance * distance) / (sigma * sigma))
|
|
if affinity < cfg.MinAffinity {
|
|
continue
|
|
}
|
|
pair := [2]int{i, n.index}
|
|
if pair[0] > pair[1] {
|
|
pair[0], pair[1] = pair[1], pair[0]
|
|
}
|
|
links = append(links, Link{
|
|
Source: indexed[pair[0]].ID, Target: indexed[pair[1]].ID,
|
|
Similarity: n.similarity, Affinity: affinity,
|
|
Confidence: clamp01(.65*n.similarity + .35*affinity),
|
|
SourceRank: rank + 1, TargetRank: 0, Reciprocal: false,
|
|
})
|
|
}
|
|
perNodeLinks[i] = links
|
|
}
|
|
})
|
|
pairs := map[[2]string]Link{}
|
|
for i := range perNodeStats {
|
|
result.Stats.BucketLookups += perNodeStats[i].BucketLookups
|
|
result.Stats.CandidatePairs += perNodeStats[i].CandidatePairs
|
|
result.Stats.ExactComparisons += perNodeStats[i].ExactComparisons
|
|
for _, link := range perNodeLinks[i] {
|
|
pair := [2]string{link.Source, link.Target}
|
|
if old, exists := pairs[pair]; !exists || link.Confidence > old.Confidence {
|
|
pairs[pair] = link
|
|
}
|
|
}
|
|
}
|
|
|
|
result.Links = make([]Link, 0, len(pairs))
|
|
for _, link := range pairs {
|
|
result.Links = append(result.Links, link)
|
|
}
|
|
sort.Slice(result.Links, func(i, j int) bool {
|
|
if result.Links[i].Source == result.Links[j].Source {
|
|
return result.Links[i].Target < result.Links[j].Target
|
|
}
|
|
return result.Links[i].Source < result.Links[j].Source
|
|
})
|
|
result.Stats.Links = len(result.Links)
|
|
return result
|
|
}
|
|
|
|
func parallelIndices(count, workers int, worker func(<-chan int)) {
|
|
if count <= 0 {
|
|
return
|
|
}
|
|
if workers < 1 {
|
|
workers = 1
|
|
}
|
|
if workers > count {
|
|
workers = count
|
|
}
|
|
jobs := make(chan int, workers*2)
|
|
var wg sync.WaitGroup
|
|
wg.Add(workers)
|
|
for i := 0; i < workers; i++ {
|
|
go func() {
|
|
defer wg.Done()
|
|
worker(jobs)
|
|
}()
|
|
}
|
|
for i := 0; i < count; i++ {
|
|
jobs <- i
|
|
}
|
|
close(jobs)
|
|
wg.Wait()
|
|
}
|
|
|
|
func bucketKey(table, band int, value uint64) uint64 {
|
|
return uint64(table&0xff)<<56 | uint64(band&0xff)<<48 | (value & 0x0000ffffffffffff)
|
|
}
|
|
|
|
func pushCoarse(h *coarseMaxHeap, candidate coarseCandidate, limit int) {
|
|
if h.Len() < limit {
|
|
heap.Push(h, candidate)
|
|
return
|
|
}
|
|
worst := (*h)[0]
|
|
if candidate.distance < worst.distance || (candidate.distance == worst.distance && candidate.index < worst.index) {
|
|
heap.Pop(h)
|
|
heap.Push(h, candidate)
|
|
}
|
|
}
|
|
|
|
func sparseSemanticHash(v []float32, table, hashBits int) uint64 {
|
|
if len(v) == 0 {
|
|
return 0
|
|
}
|
|
var signature uint64
|
|
seedBase := uint64(0x9e3779b97f4a7c15) ^ uint64(table+1)*0xbf58476d1ce4e5b9
|
|
for bit := 0; bit < hashBits; bit++ {
|
|
seed := mix64(seedBase ^ uint64(bit+1)*0x94d049bb133111eb)
|
|
var sum float32
|
|
for sample := 0; sample < 6; sample++ {
|
|
seed = mix64(seed + uint64(sample+1)*0x9e3779b97f4a7c15)
|
|
idx := int(seed % uint64(len(v)))
|
|
if seed&(1<<63) != 0 {
|
|
sum -= v[idx]
|
|
} else {
|
|
sum += v[idx]
|
|
}
|
|
}
|
|
if sum >= 0 {
|
|
signature |= 1 << bit
|
|
}
|
|
}
|
|
return signature
|
|
}
|
|
func mix64(x uint64) uint64 {
|
|
x ^= x >> 30
|
|
x *= 0xbf58476d1ce4e5b9
|
|
x ^= x >> 27
|
|
x *= 0x94d049bb133111eb
|
|
x ^= x >> 31
|
|
return x
|
|
}
|
|
func signaturesFor(v []float32, hashBits, hashTables int) []uint64 {
|
|
out := make([]uint64, hashTables)
|
|
for t := 0; t < hashTables; t++ {
|
|
out[t] = sparseSemanticHash(v, t, hashBits)
|
|
}
|
|
return out
|
|
}
|
|
func signatureDistance(a, b []uint64) int {
|
|
n := len(a)
|
|
if len(b) < n {
|
|
n = len(b)
|
|
}
|
|
d := 0
|
|
for i := 0; i < n; i++ {
|
|
d += bits.OnesCount64(a[i] ^ b[i])
|
|
}
|
|
return d
|
|
}
|
|
func cosine(a, b []float32) float64 {
|
|
if len(a) == 0 || len(a) != len(b) {
|
|
return 0
|
|
}
|
|
var dot, aa, bb float64
|
|
for i := range a {
|
|
av, bv := float64(a[i]), float64(b[i])
|
|
dot += av * bv
|
|
aa += av * av
|
|
bb += bv * bv
|
|
}
|
|
if aa == 0 || bb == 0 {
|
|
return 0
|
|
}
|
|
return dot / (math.Sqrt(aa) * math.Sqrt(bb))
|
|
}
|
|
func clamp01(v float64) float64 {
|
|
if v < 0 {
|
|
return 0
|
|
}
|
|
if v > 1 {
|
|
return 1
|
|
}
|
|
return v
|
|
}
|
|
|
|
func semanticPositions(entries []indexedEntry, adjacency [][]struct {
|
|
j int
|
|
w float64
|
|
}, smoothing float64) []Position {
|
|
raw := make([][3]float64, len(entries))
|
|
mean := [3]float64{}
|
|
for i, entry := range entries {
|
|
for axis := 0; axis < 3; axis++ {
|
|
sum := 0.0
|
|
for dim, value := range entry.Vector {
|
|
seed := mix64(uint64(dim+1)*0x9e3779b97f4a7c15 ^ uint64(axis+1)*0xbf58476d1ce4e5b9)
|
|
coeff := 1.0
|
|
if seed&(1<<63) != 0 {
|
|
coeff = -1
|
|
}
|
|
sum += float64(value) * coeff
|
|
}
|
|
raw[i][axis] = sum / math.Sqrt(float64(len(entry.Vector)))
|
|
mean[axis] += raw[i][axis]
|
|
}
|
|
}
|
|
for axis := 0; axis < 3; axis++ {
|
|
mean[axis] /= float64(len(entries))
|
|
}
|
|
std := [3]float64{}
|
|
for i := range raw {
|
|
for axis := 0; axis < 3; axis++ {
|
|
d := raw[i][axis] - mean[axis]
|
|
std[axis] += d * d
|
|
}
|
|
}
|
|
for axis := 0; axis < 3; axis++ {
|
|
std[axis] = math.Sqrt(std[axis] / float64(len(entries)))
|
|
if std[axis] < 1e-9 {
|
|
std[axis] = 1
|
|
}
|
|
}
|
|
base := make([][3]float64, len(entries))
|
|
current := make([][3]float64, len(entries))
|
|
scales := [3]float64{.72, .68, .55}
|
|
for i := range raw {
|
|
for axis := 0; axis < 3; axis++ {
|
|
base[i][axis] = math.Tanh(((raw[i][axis]-mean[axis])/std[axis])/2) * scales[axis]
|
|
current[i][axis] = base[i][axis]
|
|
}
|
|
}
|
|
if smoothing > 0 {
|
|
for iter := 0; iter < 2; iter++ {
|
|
next := make([][3]float64, len(entries))
|
|
for i := range entries {
|
|
if len(adjacency[i]) == 0 {
|
|
next[i] = current[i]
|
|
continue
|
|
}
|
|
var avg [3]float64
|
|
total := 0.0
|
|
for _, n := range adjacency[i] {
|
|
total += n.w
|
|
for axis := 0; axis < 3; axis++ {
|
|
avg[axis] += current[n.j][axis] * n.w
|
|
}
|
|
}
|
|
if total > 0 {
|
|
for axis := 0; axis < 3; axis++ {
|
|
avg[axis] /= total
|
|
next[i][axis] = (1-smoothing)*base[i][axis] + smoothing*avg[axis]
|
|
}
|
|
} else {
|
|
next[i] = current[i]
|
|
}
|
|
}
|
|
current = next
|
|
}
|
|
}
|
|
current = spreadDenseLayout(entries, current)
|
|
out := make([]Position, len(entries))
|
|
for i, entry := range entries {
|
|
out[i] = Position{ID: entry.ID, X: current[i][0], Y: current[i][1], Z: current[i][2]}
|
|
}
|
|
return out
|
|
}
|
|
|
|
type layoutCellKey struct{ x, y, z int }
|
|
type layoutCell struct {
|
|
count int
|
|
sum [3]float64
|
|
}
|
|
|
|
func spreadDenseLayout(entries []indexedEntry, current [][3]float64) [][3]float64 {
|
|
if len(current) == 0 {
|
|
return current
|
|
}
|
|
const cellSize = .08
|
|
for iter := 0; iter < 2; iter++ {
|
|
cells := make(map[layoutCellKey]layoutCell, len(current)/4)
|
|
keys := make([]layoutCellKey, len(current))
|
|
for i, p := range current {
|
|
key := layoutCellKey{int(math.Floor(p[0] / cellSize)), int(math.Floor(p[1] / cellSize)), int(math.Floor(p[2] / cellSize))}
|
|
keys[i] = key
|
|
c := cells[key]
|
|
c.count++
|
|
for a := 0; a < 3; a++ {
|
|
c.sum[a] += p[a]
|
|
}
|
|
cells[key] = c
|
|
}
|
|
next := make([][3]float64, len(current))
|
|
copy(next, current)
|
|
for i, p := range current {
|
|
c := cells[keys[i]]
|
|
if c.count <= 10 {
|
|
continue
|
|
}
|
|
centroid := [3]float64{}
|
|
for a := 0; a < 3; a++ {
|
|
centroid[a] = c.sum[a] / float64(c.count)
|
|
}
|
|
d := [3]float64{p[0] - centroid[0], p[1] - centroid[1], p[2] - centroid[2]}
|
|
norm := math.Sqrt(d[0]*d[0] + d[1]*d[1] + d[2]*d[2])
|
|
if norm < 1e-8 {
|
|
seed := mix64(uint64(i+1) ^ uint64(len(entries[i].ID))*0x9e3779b97f4a7c15)
|
|
for a := 0; a < 3; a++ {
|
|
if (seed>>uint(a))&1 == 0 {
|
|
d[a] = 1
|
|
} else {
|
|
d[a] = -1
|
|
}
|
|
}
|
|
norm = math.Sqrt(3)
|
|
}
|
|
strength := math.Min(.028, .0045*math.Log1p(float64(c.count-10)))
|
|
for a := 0; a < 3; a++ {
|
|
next[i][a] += (d[a] / norm) * strength
|
|
}
|
|
}
|
|
current = next
|
|
}
|
|
return current
|
|
}
|