Inverted file system with asymmetric distance computation for billion-scale approximate nearest neighbor search.

Installation

using Pkg
Pkg.add("IVFADC")

or

Pkg.add(PackageSpec(url="https://github.com/JuliaNeighbors/IVFADC.jl", rev="master"))

for the latest master branch.

Examples

Create an index

using IVFADC
using Distances

nrows, nvectors = 50, 1_000
data = rand(Float32, nrows, nvectors)

kc = 100  # coarse vectors (i.e. Voronoi cells)
k = 256   # residual quantization levels/codebook
m = 10	  # residual quantizer codebooks

ivfadc = IVFADCIndex(data,
                     kc=kc,
                     k=k,
                     m=m,
                     coarse_quantizer=:naive,
                     coarse_distance=SqEuclidean(),
                     quantization_distance=SqEuclidean(),
                     quantization_method=:pq,
                     index_type=UInt16)
# IVFADCIndex, naive coarse quantizer, 12-byte encoding (2 + 1×10), 1000 Float32 vectors

Add and delete points to the index

Points can be added to the index by using the push! and pushfirst! methods. Removing points from the index can be performed using the pop!, popfirst! and delete_from_index! methods.

for i in 1:15
    push!(ivfadc, rand(Float32, nrows))
end
length(ivfadc)
# 1015

delete_from_index!(ivfadc, [1000, 1001, 1010, 1015])
length(ivfadc)
# 1011

The pop! and popfirst! methods also return the indexed (and quantized) vectors respectively.

pop!(ivfadc)
# 50-element Array{Float32,1}:
#   0.30565456
#   0.6903644
#   ⋮
#   0.20116138
#   0.90699536

popfirst!(ivfadc)
# 50-element Array{Float32,1}:
#  0.29412186
#  0.0709379
#  ⋮
#  0.51727176
#  0.69718516

length(ivfadc)
# 09

Search the index

point = data[:, 123];
idxs, dists = knn_search(ivfadc, point, 3)
# (UInt16[0x007a, 0x0237, 0x0081], Float32[4.303085, 10.026548, 10.06385])

int_idxs = Int.(idxs) .+ 1  # retrieve 1-based integer neighbors
# 3-element Array{Int64,1}:
#  123
#  568
#  130

Features

To keep track with the latest features, please consult NEWS.md and the documentation.

License

The code has an MIT license and therefore it is free.

Reporting Bugs

This is work in progress and bugs may still be present...¯\(ツ)/¯ Do not worry, just open an issue to report a bug or request a feature.

References

• Jègou et al. "Product quantization for nearest neighbor search", IEEE TPAMI, 2011
• Baranchuk et al. "Revisiting the inverted indices for billion-scale approximate nearest neighbors, ECCV, 2018"