vptree

README

vptree

Description

In-memory VPTree for efficient searching of uint64 hash. Designed to be used with Perceptual Hashing. Useful for searching Image hashes produced by github.com/corona10/goimagehash

TODO:

[ ] Write tests [ ] Improve benchmarks

Benchmarks

LinearSearch compared with VPTree Search on dataset of ~20000. VPTree search will improve compared to linear Search with decreased tau and increased number of items.

    name          old time/op  new time/op  delta
    Search/2-12   22.3µs ± 3%   7.1µs ± 6%  -68.30%  (p=0.000 n=20+20)
    Search/4-12   22.4µs ± 6%  10.7µs ± 6%  -52.11%  (p=0.000 n=20+19)
    Search/6-12   22.6µs ± 4%  15.9µs ± 5%  -29.71%  (p=0.000 n=20+20)
    Search/8-12   22.9µs ± 5%  18.0µs ± 5%  -21.40%  (p=0.000 n=20+19)
    Search/10-12  22.8µs ± 5%  19.6µs ± 5%  -13.79%  (p=0.000 n=20+20)
    Search/12-12  22.6µs ± 4%  19.7µs ± 4%  -12.88%  (p=0.000 n=20+20)
    Search/14-12  22.8µs ± 4%  20.0µs ± 5%  -12.14%  (p=0.000 n=19+20)

Search Benchmarks compared for 1,000,000 items:

//cpu: AMD Ryzen 5 5600X 6-Core Processor
//BenchmarkSearch/16-12   	    1167	   1045384 ns/op	     160 B/op	       4 allocs/op
//BenchmarkSimStore/16-12 	      79	  14379709 ns/op	    2816 B/op	      94 allocs/op

Inspired by

github.com/dgryski/go-simstore

Contributing

Please create a PR. Would appreciate contributions.

Authors

Evan Oberholster (2022)

License

MIT License

Documentation

Overview

Package vptree is an implementation of Vantage Point Trees in Go for bit hash of uint64. It is ideally suited for image similarity using an uint64 hash

Index

• type Results
  • func LinearSearch(arr []uint64, query uint64, tau uint64, k int) (r *Results)
  • func (r Results) Array() ([]uint64, []uint8)
  • func (r Results) Len() int
  • func (r Results) Less(i, j int) bool
  • func (r *Results) Pop() (item uint64, dist uint64)
  • func (r *Results) Push(item uint64, dist uint64)
  • func (r Results) Swap(i, j int)
  • func (r Results) Top() (item uint64, dist uint64)
• type VPTree
  • func NewVPTree() *VPTree
  • func NewVPTreeConcurrent() *VPTree
  • func (vp *VPTree) Add(item uint64)
  • func (vp *VPTree) AddConcurrent(item uint64)
  • func (vp *VPTree) Close()
  • func (vp *VPTree) Search(query uint64, tau uint64, k int) (r *Results)
  • func (vp *VPTree) SearchConcurrent(query uint64, tau uint64, k int) (r *Results)

Types

type Results

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

Results are the VPTree search results

func LinearSearch

func LinearSearch(arr []uint64, query uint64, tau uint64, k int) (r *Results)

Search an arr using Linear Search with the given query, tau, and k

func (Results) Array

func (r Results) Array() ([]uint64, []uint8)

Array returns VPTree search results as 2 arrays. arrays are always equally lengthed.

func (Results) Len

func (r Results) Len() int

func (Results) Less

func (r Results) Less(i, j int) bool

func (*Results) Pop

func (r *Results) Pop() (item uint64, dist uint64)

Pop removes and returns the minimum element (according to Less) from the heap. The complexity is O(log n) where n = h.Len(). Pop is equivalent to Remove(h, 0).

func (*Results) Push

func (r *Results) Push(item uint64, dist uint64)

Push adds an item and dist to the underlying Results

func (Results) Swap

func (r Results) Swap(i, j int)

func (Results) Top

func (r Results) Top() (item uint64, dist uint64)

Top returns the largest distance between

type VPTree

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

VPTree is a vantage point tree

func NewVPTree

func NewVPTree() *VPTree

NewVPTree returns a new VPTree

func NewVPTreeConcurrent

func NewVPTreeConcurrent() *VPTree

NewVPTreeConcurrent returns a new VPTree with locking features

func (*VPTree) Add

func (vp *VPTree) Add(item uint64)

Add adds an item to the given VPTree

func (*VPTree) AddConcurrent

func (vp *VPTree) AddConcurrent(item uint64)

func (*VPTree) Close

func (vp *VPTree) Close()

func (*VPTree) Search

func (vp *VPTree) Search(query uint64, tau uint64, k int) (r *Results)

Search a VPTree given the following query, tau, and k

func (*VPTree) SearchConcurrent

func (vp *VPTree) SearchConcurrent(query uint64, tau uint64, k int) (r *Results)