mirror of
https://github.com/hanzoai/graph.git
synced 2026-10-30 18:35:37 +00:00
zeekay
f5aaeb712e
Derived from Dgraph (github.com/dgraph-io/dgraph) at commit 64804bd2, Apache-2.0. See NOTICE. WHAT THIS IS. The graph engine as a Go library: posting lists, the DQL parser, the type and tokenizer system, the index and schema layers, and the wire types. 39,170 lines of the upstream's 166,337. THE STORE is github.com/luxfi/zapdb, a Badger fork that kept the package name, the subpackages (options, pb, y) and the API — Open, OpenManaged, DB, Options — so the 74 import sites are aliased rather than rewritten. THE CODEC is ZAP. zapdb serializes with ZAP, not protobuf: its pb package builds the ZAP types by default and the protobuf ones only under `-tags grpc`, a path that does not compile (table/builder.go calls pb.Marshal, which that tag removes). One call site in posting needed converting; every other type here is Hanzo's own protobuf and is untouched. NO TRANSPORT. An embedded engine dials nothing, so nothing here imports google.golang.org/grpc. Removed: 20 transport functions in x, the generated service stubs for Raft, Zero and Worker (1,657 lines), and the JWT helper — identity belongs to IAM. The core called none of them. NOT KEPT: worker, conn, raftwal, the cluster commands, the GraphQL layer and the test harnesses. `query`, the DQL execution engine, went with them because it depends on worker; parsing DQL is available here, executing it is not. The history of the upstream project lives at github.com/dgraph-io/dgraph. This repository begins at the derivation because three quarters of that history describes code this fork does not carry.
174 lines
4.4 KiB
Go
174 lines
4.4 KiB
Go
/*
|
|
* SPDX-FileCopyrightText: © 2017-2026 Istari Digital, Inc.
|
|
* SPDX-License-Identifier: Apache-2.0
|
|
*/
|
|
|
|
package hnsw
|
|
|
|
import (
|
|
"container/heap"
|
|
|
|
c "github.com/hanzoai/graph/tok/constraints"
|
|
)
|
|
|
|
const notAUid uint64 = 0
|
|
|
|
type persistentHeapElement[T c.Float] struct {
|
|
value T
|
|
index uint64
|
|
// An element that is "filteredOut" is one that should be removed
|
|
// from final consideration due to it not matching the passed in
|
|
// filter criteria.
|
|
filteredOut bool
|
|
}
|
|
|
|
func initPersistentHeapElement[T c.Float](
|
|
val T, i uint64, filteredOut bool) *persistentHeapElement[T] {
|
|
return &persistentHeapElement[T]{
|
|
value: val,
|
|
index: i,
|
|
filteredOut: filteredOut,
|
|
}
|
|
}
|
|
|
|
type minPersistentTupleHeap[T c.Float] []persistentHeapElement[T]
|
|
|
|
func (h minPersistentTupleHeap[T]) Len() int {
|
|
return len(h)
|
|
}
|
|
|
|
func (h minPersistentTupleHeap[T]) Less(i, j int) bool {
|
|
return h[i].value < h[j].value
|
|
}
|
|
|
|
func (h minPersistentTupleHeap[T]) Swap(i, j int) {
|
|
h[i], h[j] = h[j], h[i]
|
|
}
|
|
|
|
func (h *minPersistentTupleHeap[T]) Push(x interface{}) {
|
|
*h = append(*h, x.(persistentHeapElement[T]))
|
|
}
|
|
|
|
func (h *minPersistentTupleHeap[T]) PopLast() {
|
|
heap.Remove(h, h.Len()-1)
|
|
}
|
|
|
|
func (h *minPersistentTupleHeap[T]) Pop() interface{} {
|
|
old := *h
|
|
n := len(old)
|
|
x := old[n-1]
|
|
*h = old[:n-1]
|
|
return x
|
|
}
|
|
|
|
// buildMinPersistentHeapByInit will create a min-heap for distance metrics
|
|
// in time O(n), where n = length of array
|
|
func buildMinPersistentHeapByInit[T c.Float](array []persistentHeapElement[T]) *minPersistentTupleHeap[T] {
|
|
// initialize the MinTupleHeap that has implement the heap.Interface
|
|
minPersistentTupleHeap := &minPersistentTupleHeap[T]{}
|
|
*minPersistentTupleHeap = array
|
|
heap.Init(minPersistentTupleHeap)
|
|
return minPersistentTupleHeap
|
|
}
|
|
|
|
// maxPersistentTupleHeap is a max-heap for similarity metrics (cosine, dot-product)
|
|
// where higher values indicate better matches.
|
|
type maxPersistentTupleHeap[T c.Float] []persistentHeapElement[T]
|
|
|
|
func (h maxPersistentTupleHeap[T]) Len() int {
|
|
return len(h)
|
|
}
|
|
|
|
func (h maxPersistentTupleHeap[T]) Less(i, j int) bool {
|
|
return h[i].value > h[j].value // reversed for max-heap
|
|
}
|
|
|
|
func (h maxPersistentTupleHeap[T]) Swap(i, j int) {
|
|
h[i], h[j] = h[j], h[i]
|
|
}
|
|
|
|
func (h *maxPersistentTupleHeap[T]) Push(x interface{}) {
|
|
*h = append(*h, x.(persistentHeapElement[T]))
|
|
}
|
|
|
|
func (h *maxPersistentTupleHeap[T]) PopLast() {
|
|
heap.Remove(h, h.Len()-1)
|
|
}
|
|
|
|
func (h *maxPersistentTupleHeap[T]) Pop() interface{} {
|
|
old := *h
|
|
n := len(old)
|
|
x := old[n-1]
|
|
*h = old[:n-1]
|
|
return x
|
|
}
|
|
|
|
// buildMaxPersistentHeapByInit will create a max-heap for similarity metrics
|
|
// in time O(n), where n = length of array
|
|
func buildMaxPersistentHeapByInit[T c.Float](array []persistentHeapElement[T]) *maxPersistentTupleHeap[T] {
|
|
maxHeap := &maxPersistentTupleHeap[T]{}
|
|
*maxHeap = array
|
|
heap.Init(maxHeap)
|
|
return maxHeap
|
|
}
|
|
|
|
// candidateHeap is an interface for the candidate heap used in HNSW search.
|
|
// It abstracts over min-heap (for distance metrics) and max-heap (for similarity metrics).
|
|
type candidateHeap[T c.Float] interface {
|
|
Len() int
|
|
Push(x persistentHeapElement[T])
|
|
Pop() persistentHeapElement[T]
|
|
PopLast()
|
|
}
|
|
|
|
// minHeapWrapper wraps minPersistentTupleHeap to implement candidateHeap interface
|
|
type minHeapWrapper[T c.Float] struct {
|
|
h *minPersistentTupleHeap[T]
|
|
}
|
|
|
|
func (w *minHeapWrapper[T]) Len() int {
|
|
return w.h.Len()
|
|
}
|
|
|
|
func (w *minHeapWrapper[T]) Push(x persistentHeapElement[T]) {
|
|
heap.Push(w.h, x)
|
|
}
|
|
|
|
func (w *minHeapWrapper[T]) Pop() persistentHeapElement[T] {
|
|
return heap.Pop(w.h).(persistentHeapElement[T])
|
|
}
|
|
|
|
func (w *minHeapWrapper[T]) PopLast() {
|
|
w.h.PopLast()
|
|
}
|
|
|
|
// maxHeapWrapper wraps maxPersistentTupleHeap to implement candidateHeap interface
|
|
type maxHeapWrapper[T c.Float] struct {
|
|
h *maxPersistentTupleHeap[T]
|
|
}
|
|
|
|
func (w *maxHeapWrapper[T]) Len() int {
|
|
return w.h.Len()
|
|
}
|
|
|
|
func (w *maxHeapWrapper[T]) Push(x persistentHeapElement[T]) {
|
|
heap.Push(w.h, x)
|
|
}
|
|
|
|
func (w *maxHeapWrapper[T]) Pop() persistentHeapElement[T] {
|
|
return heap.Pop(w.h).(persistentHeapElement[T])
|
|
}
|
|
|
|
func (w *maxHeapWrapper[T]) PopLast() {
|
|
w.h.PopLast()
|
|
}
|
|
|
|
// buildCandidateHeap creates the appropriate heap based on whether we're using
|
|
// a distance metric (lower is better) or similarity metric (higher is better).
|
|
func buildCandidateHeap[T c.Float](array []persistentHeapElement[T], isSimilarityMetric bool) candidateHeap[T] {
|
|
if isSimilarityMetric {
|
|
return &maxHeapWrapper[T]{h: buildMaxPersistentHeapByInit(array)}
|
|
}
|
|
return &minHeapWrapper[T]{h: buildMinPersistentHeapByInit(array)}
|
|
}
|