Skip to content
Go to file
Cannot retrieve contributors at this time
47 lines (45 sloc) 2.14 KB
Adding a parameter SearchParams::S which is the online
equivalence of IndexParams::S. At search time, all
neighbors or a neighbor are visited at the same time
in the original algorithm. With the new behavior,
neighbors are visited in batches of SearchParams::S.
k-NN working list: a b c d e [f] g
[l m n] o p q
we are at entry f, and visiting it's first batch of
neighbors l, m and n. Suppose m and n are actually
better than f and g, the working space will become
a b c d e [m] n
We'll then directly move on to check m's neighbors,
as apposed to finish checking f's neighbors o p and q.
Default is set to default_s = 10 which is the same for
Enabling edge reversing for better search performance.
The original index is the exact k-NN graph, and has
difficulties to reach very high recall (>0.98) for some
difficult datasets. The problem is that the k-NN graph
is a directed graph and k is the out-digree. That means
the in-digree of a node might have very high variance.
If a node happen to have 0 in-dgree, then it's not
possible to reach this node in graph-based search process.
The idea of edge reversing is to add the reverse edges
to the original graph for the index. A new parameter
IndexParams::reverse is introduced and has the following
0 : (default) do not add reverse edges.
-1 : add reverse edges automatically using M values.
k>0: trim the graph into a k-NN graph and add all
the reverse edges.
All source code using KGraph should be backward compatible,
with a default value of IndexParams::reverse set to 0.
For the purpose of index construction, it is recommend that
the value be set to -1.
Changin file format.
Chaning to VERSION_MAJOR only, renamed as SIGNATURE_VERSION
Using VERSION_MINOR to denote file capabiliy (SIGNATURE_CAP), which defaults to 0
and is compatible to original scheme.
You can’t perform that action at this time.