Solving single queries

Solving single queries and KnnResult

By Eric S. Téllez

using SimilaritySearch

This example shows how to perform single queries instead of solving a batch of them. This is particularly useful for some applications, and we also show how they are solved, which could be used to avoid some memory allocations.

const dim = 8

db = MatrixDatabase(randn(Float32, dim, 10^4))
dist = SqL2Distance()
G = SearchGraph(; dist, db, verbose=false)
index!(G)

Suppose you want to compute some $k$ nearest neighbors, for this we use the structure KnnResult which is a priority queue of maximum size k.

res = KnnResult(3) # allocates memory for 10 nearest neighbors
for v in rand(db, 10)
    global res = reuse!(res)  # reuses the res object
    @time search(G, v, res)
    @show minimum(res), maximum(res), argmin(res), argmax(res)
    @show res
end

  0.000020 seconds (3 allocations: 64 bytes)
(minimum(res), maximum(res), argmin(res), argmax(res)) = (0.0f0, 2.2056494f0, 0x000023b4, 0x000000c7)
res = SimilaritySearch.KnnResult(SimilaritySearch.AdjacencyLists.IdWeight[SimilaritySearch.AdjacencyLists.IdWeight(0x000023b4, 0.0f0), SimilaritySearch.AdjacencyLists.IdWeight(0x0000012d, 1.8902102f0), SimilaritySearch.AdjacencyLists.IdWeight(0x000000c7, 2.2056494f0)], 3)
  0.000024 seconds (3 allocations: 64 bytes)
(minimum(res), maximum(res), argmin(res), argmax(res)) = (1.0968232f0, 1.7169907f0, 0x00000d73, 0x00001e2e)
res = SimilaritySearch.KnnResult(SimilaritySearch.AdjacencyLists.IdWeight[SimilaritySearch.AdjacencyLists.IdWeight(0x00000d73, 1.0968232f0), SimilaritySearch.AdjacencyLists.IdWeight(0x00001b25, 1.7053723f0), SimilaritySearch.AdjacencyLists.IdWeight(0x00001e2e, 1.7169907f0)], 3)
  0.000013 seconds (3 allocations: 64 bytes)
(minimum(res), maximum(res), argmin(res), argmax(res)) = (0.0f0, 1.1839159f0, 0x0000193f, 0x000006b1)
res = SimilaritySearch.KnnResult(SimilaritySearch.AdjacencyLists.IdWeight[SimilaritySearch.AdjacencyLists.IdWeight(0x0000193f, 0.0f0), SimilaritySearch.AdjacencyLists.IdWeight(0x0000132b, 1.0716056f0), SimilaritySearch.AdjacencyLists.IdWeight(0x000006b1, 1.1839159f0)], 3)
  0.000006 seconds (3 allocations: 64 bytes)
(minimum(res), maximum(res), argmin(res), argmax(res)) = (2.0062492f0, 2.639026f0, 0x0000018f, 0x00001013)
res = SimilaritySearch.KnnResult(SimilaritySearch.AdjacencyLists.IdWeight[SimilaritySearch.AdjacencyLists.IdWeight(0x0000018f, 2.0062492f0), SimilaritySearch.AdjacencyLists.IdWeight(0x0000235c, 2.5218146f0), SimilaritySearch.AdjacencyLists.IdWeight(0x00001013, 2.639026f0)], 3)
  0.000011 seconds (3 allocations: 64 bytes)
(minimum(res), maximum(res), argmin(res), argmax(res)) = (0.0f0, 0.9671448f0, 0x000016df, 0x0000234b)
res = SimilaritySearch.KnnResult(SimilaritySearch.AdjacencyLists.IdWeight[SimilaritySearch.AdjacencyLists.IdWeight(0x000016df, 0.0f0), SimilaritySearch.AdjacencyLists.IdWeight(0x00002178, 0.7287925f0), SimilaritySearch.AdjacencyLists.IdWeight(0x0000234b, 0.9671448f0)], 3)
  0.000011 seconds (3 allocations: 64 bytes)
(minimum(res), maximum(res), argmin(res), argmax(res)) = (0.0f0, 0.71299195f0, 0x000022cc, 0x0000026d)
res = SimilaritySearch.KnnResult(SimilaritySearch.AdjacencyLists.IdWeight[SimilaritySearch.AdjacencyLists.IdWeight(0x000022cc, 0.0f0), SimilaritySearch.AdjacencyLists.IdWeight(0x00001d89, 0.33901426f0), SimilaritySearch.AdjacencyLists.IdWeight(0x0000026d, 0.71299195f0)], 3)
  0.000014 seconds (3 allocations: 64 bytes)
(minimum(res), maximum(res), argmin(res), argmax(res)) = (0.0f0, 0.9490801f0, 0x00001f56, 0x0000077c)
res = SimilaritySearch.KnnResult(SimilaritySearch.AdjacencyLists.IdWeight[SimilaritySearch.AdjacencyLists.IdWeight(0x00001f56, 0.0f0), SimilaritySearch.AdjacencyLists.IdWeight(0x000004c7, 0.828595f0), SimilaritySearch.AdjacencyLists.IdWeight(0x0000077c, 0.9490801f0)], 3)
  0.000010 seconds (3 allocations: 64 bytes)
(minimum(res), maximum(res), argmin(res), argmax(res)) = (0.0f0, 0.9363507f0, 0x00000962, 0x000000d0)
res = SimilaritySearch.KnnResult(SimilaritySearch.AdjacencyLists.IdWeight[SimilaritySearch.AdjacencyLists.IdWeight(0x00000962, 0.0f0), SimilaritySearch.AdjacencyLists.IdWeight(0x000026c9, 0.6484516f0), SimilaritySearch.AdjacencyLists.IdWeight(0x000000d0, 0.9363507f0)], 3)
  0.000005 seconds (3 allocations: 64 bytes)
(minimum(res), maximum(res), argmin(res), argmax(res)) = (0.0f0, 3.4429328f0, 0x000016cc, 0x00000445)
res = SimilaritySearch.KnnResult(SimilaritySearch.AdjacencyLists.IdWeight[SimilaritySearch.AdjacencyLists.IdWeight(0x000016cc, 0.0f0), SimilaritySearch.AdjacencyLists.IdWeight(0x00001099, 2.4439046f0), SimilaritySearch.AdjacencyLists.IdWeight(0x00000445, 3.4429328f0)], 3)
  0.000009 seconds (3 allocations: 64 bytes)
(minimum(res), maximum(res), argmin(res), argmax(res)) = (0.0f0, 0.98899597f0, 0x0000007b, 0x000020b5)
res = SimilaritySearch.KnnResult(SimilaritySearch.AdjacencyLists.IdWeight[SimilaritySearch.AdjacencyLists.IdWeight(0x0000007b, 0.0f0), SimilaritySearch.AdjacencyLists.IdWeight(0x00000d1b, 0.9774504f0), SimilaritySearch.AdjacencyLists.IdWeight(0x000020b5, 0.98899597f0)], 3)

KnnResult

This structure is the container for the result and it is also used to specify the number of elements to retrieve. As mentioned before, it is a priority queue

res = reuse!(res)
push_item!(res, 1, 10)
push_item!(res, 2, 9)
push_item!(res, 3, 8)
push_item!(res, 4, 7)
push_item!(res, 6, 5)
@show res

res = SimilaritySearch.KnnResult(SimilaritySearch.AdjacencyLists.IdWeight[SimilaritySearch.AdjacencyLists.IdWeight(0x00000006, 5.0f0), SimilaritySearch.AdjacencyLists.IdWeight(0x00000004, 7.0f0), SimilaritySearch.AdjacencyLists.IdWeight(0x00000003, 8.0f0)], 3)

it also supports removals

@show :popfirst! => popfirst!(res)
push_item!(res, 7, 0.1)
@show :push_item! => res
@show :pop! => pop!(res)
res

:popfirst! => popfirst!(res) = :popfirst! => SimilaritySearch.AdjacencyLists.IdWeight(0x00000006, 5.0f0)
:push_item! => res = :push_item! => SimilaritySearch.KnnResult(SimilaritySearch.AdjacencyLists.IdWeight[SimilaritySearch.AdjacencyLists.IdWeight(0x00000007, 0.1f0), SimilaritySearch.AdjacencyLists.IdWeight(0x00000004, 7.0f0), SimilaritySearch.AdjacencyLists.IdWeight(0x00000003, 8.0f0)], 3)
:pop! => pop!(res) = :pop! => SimilaritySearch.AdjacencyLists.IdWeight(0x00000003, 8.0f0)
SimilaritySearch.KnnResult(SimilaritySearch.AdjacencyLists.IdWeight[SimilaritySearch.AdjacencyLists.IdWeight(0x00000007, 0.1f0), SimilaritySearch.AdjacencyLists.IdWeight(0x00000004, 7.0f0)], 3)

It can be iterated

@show collect(res)

collect(res) = SimilaritySearch.AdjacencyLists.IdWeight[SimilaritySearch.AdjacencyLists.IdWeight(0x00000007, 0.1f0), SimilaritySearch.AdjacencyLists.IdWeight(0x00000004, 7.0f0)]

Dependencies

Status `~/Research/SimilaritySearchDemos/site-src/Project.toml`
  [053f045d] SimilaritySearch v0.10.8