factory_string.bnf

# definition of all indexes

Index ::=
	{ VectorTransform "," }+ Index |     # IndexPreTransform
	Index ",RFlat" |                     # IndexRefine
	Index ",Refine(" Index ")" |         # IndexRefine
	Index ",IDMap" |                     # IndexIDMap
	IndexIVF |
	IndexHNSW |
	IndexNSG |
	IndexFlatCodes |
	IndexLattice |
	AdditiveCoarseQuantizer              # The 2 flavors of addtive coarse quantizers


# supported scalar quantizer types
SQtype ::= "SQ4" | "SQ8" | "SQ6" | "SQfp16"

# supported product quantizer types
PQtype ::= "PQ" int {"x" int} "np"?

# supported 4-bit PQ fast-scan types
PQfsType ::= "PQ" int "x4fs" | "PQ" int "x4fs_" int

# additive quantization description of the form 1x2_3x4
aq_groups ::= int "x" int { "_" int "x" int }*

# additive quantization norm encodings
aq_norm ::=
	"_None" | "_Nfloat" | "_Nqint8" | "_Nqint4" |
	"_Ncqint8" | "_Ncqint4"

# Flat index variants
IndexFlatCodes ::=
	"Flat" |                      # IndexFlat
	PQtype |                      # IndexPQ
	SQtype |                      # IndexScalarQuantizer
	"LSH" "r"? "t"? |             # IndexLSH
	PQfsType |                    # IndexPQFastScan
	"RQ" aq_groups aq_norm |      # IndexResidualQuantizer
	"LSQ" aq_groups aq_norm       # IndexLocalSearchQuantizer

# additive quantizers used as coarse quantizers
# (the values are centroids, not explict)
AdditiveCoarseQuantizer ::=
	"RCQ" aq_groups aq_norm |     # ResidualCoarseQuantizer
	"LSCQ" aq_groups aq_norm      # LocalSearchCoarseQuantizer

# variants of HNSW
IndexHNSW ::=
	"HNSW" int? ",Flat" |         # IndexHNSWFlat
	"HNSW" int? "_PQ" int |       # IndexHNSWPQ
    	"HNSW" int? "_" SQtype |
	"HNSW" int? "_" int "+PQ" int |
	"HNSW" int? "_2x" int "+PQ" int

# search graph
IndexNSG ::= "NSG" int ",Flat"

# ways to specify a coarse quantizer
ivf_component ::=
	"IVF" int |                    # IndexFlat coarse quantizer
	"IVF" int "_HNSW" int? |       # IndexHNSWFlat coarse quantizer
	"IVF" int "_NSG" int |         # IndexNSG coarse quantizer
	"IMI2x" int |                  # MultiIndexQuantizer
	"IVF" int "(" Index ")" |      # arbitrary

# inverted list variants
IndexIVF ::=
	ivf_component "," PQtype |                # IndexIVFPQ
	ivf_component "," PQfsType "r"? |         # IndeXIVFPQFastScan
	ivf_component ",PQ" int "+" int |         # IndexIVFPQR
	ivf_component "," SQtype |                # IndexIVFScalarQuantizer
	ivf_component { ",ITQ" | ",PCAR" } int ",SH" float? |   # IndexIVFSperctralHash
	ivf_component ",RQ"  aq_type aq_groups aq_norm |  # IndexIVFResidualQuantizer
	ivf_component ",LSQ" aq_type aq_groups aq_norm    # IndexIVFLocalSearchQuantizer

# vector transforms used in IndexPreTransform
VectorTransform ::=
	"PCA" ["W"] ["R"] int |    # PCAMatrix
	"OPQ" int [ "_" int ] |    # OPQMatrix
    	"RR" int? |                # RandomRotation
	"ITQ" [ int ] |            # ITQMatrix
	"Pad" int |
	"L2norm"

IndexLattice ::=
	"ZnLattice" int "x" int "_" int