A local vector index for retrieval: store embedding vectors under string ids and ask for the nearest ones. Search is exact (a scan of every vector) for cosine similarity, dot product and Euclidean distance. Compile with -lib ml_vector,gen_collect; it needs nothing from System.ML. Design and measurements: docs/AI.md, "Local vector search".
VectorIndex
An exact nearest-neighbour index over Float vectors of one fixed dimension, each stored under a unique String id.
No call here ends the program on bad input. Add, Remove and Store return false, Search returns an empty vector and Get returns Nil, and GetError() on that index says why. Load is a function with no index to ask, so it returns Nil and gives no reason. An index made with a dimension below 1 is not valid (IsValid() is false) and refuses everything.
Values: NaN and infinity are refused, and so is any nonzero value whose magnitude is below 1e-100 or above 1e100 (zero is fine). Inside that range no square, sum of squares, difference or product can overflow or underflow, so every score is finite; outside it a norm would become infinity or zero and a cosine would silently read 0. Rescale such data before adding it.
A search scans every stored vector, so the cost is size x dimension; there is no approximate mode. Ties on the score are broken by id, smallest first, so results do not depend on the order vectors were added or removed in. That holds for bit-identical scores: two vectors that tie only mathematically (parallel vectors of different length under COSINE, say) can differ in the last bit and then rank by that bit and not by id. COSINE scores are clamped to [-1, 1].
Not thread-safe: Search records its refusals in the index, so concurrent calls on one index (or a call beside Add or Remove) need the caller's lock. Memory: 8 bytes per value; the first Add at the largest dimension (1,048,576) allocates a 128 MB block, and Load holds the file, its body and the decoded vectors at once, about three times the file size at its peak.
Example
index := VectorIndex->New(3, VectorMetric->COSINE);
index->Add("cat", [0.9, 0.1, 0.0]);
index->Add("car", [0.0, 0.2, 0.9]);
hits := index->Search([1.0, 0.0, 0.0], 1);
hits->Get(0)->GetId()->PrintLine(); # cat
index->Store("pets.vix");Operations
Add #
Stores a vector under an id; an id that is already present has its vector replaced. The vector is copied.
method : public : Add(id:String, vector:Float[]) ~ BoolParameters
| Name | Type | Description |
|---|---|---|
| id | String | unique id, not Nil or empty |
| vector | Float | vector of exactly the index's dimension; each value finite and zero or between 1e-100 and 1e100 in magnitude |
Return
| Type | Description |
|---|---|
| Bool | true if stored, false if refused (GetError() says why) |
Contains #
Whether a vector is stored under an id.
method : public : Contains(id:String) ~ BoolParameters
| Name | Type | Description |
|---|---|---|
| id | String | id to look for |
Return
| Type | Description |
|---|---|
| Bool | true if present |
Get #
A copy of the vector stored under an id.
method : public : Get(id:String) ~ Float[]Parameters
| Name | Type | Description |
|---|---|---|
| id | String | id to look up |
Return
| Type | Description |
|---|---|
| Float | the vector, or Nil if there is none |
GetDimension #
Length of the vectors this index holds.
method : public : GetDimension() ~ IntReturn
| Type | Description |
|---|---|
| Int | dimension, 0 for an invalid index |
GetError #
The message for the last call that refused its input, or an empty string.
method : public : GetError() ~ StringReturn
| Type | Description |
|---|---|
| String | reason |
GetIds #
All stored ids, in no particular order.
method : public : GetIds() ~ Vector<String>Return
| Type | Description |
|---|---|
| Vector<String> | ids, empty if the index is invalid |
GetMetric #
The ranking this index was created with.
method : public : GetMetric() ~ VectorMetricReturn
| Type | Description |
|---|---|
| VectorMetric | metric |
IsValid #
Whether the index was created with a usable dimension.
method : public : IsValid() ~ BoolReturn
| Type | Description |
|---|---|
| Bool | true if it accepts vectors |
Load # function
Reads an index written by Store. A file that is missing, is not an index, is from a newer format, or fails its CRC32 (truncated, or damaged) gives Nil rather than ending the program.
function : Load(filename:String) ~ VectorIndexParameters
| Name | Type | Description |
|---|---|---|
| filename | String | file to read |
Return
| Type | Description |
|---|---|
| VectorIndex | the index, or Nil |
New # constructor
Creates an empty index.
New(dim:Int, metric:VectorMetric)Parameters
| Name | Type | Description |
|---|---|---|
| dim | Int | length of every vector, 1 or more |
| metric | VectorMetric | how vectors are ranked against a query |
Remove #
Removes a vector.
method : public : Remove(id:String) ~ BoolParameters
| Name | Type | Description |
|---|---|---|
| id | String | id to remove |
Return
| Type | Description |
|---|---|
| Bool | true if it was present, false if not (or the id is Nil) |
Search #
The k closest vectors to a query, closest first. Fewer than k come back when the index holds fewer, and none when the query is refused (Nil, the wrong length, a NaN, an infinite or out-of-range value, k below 1) or the index is empty; GetError() says which. COSINE scores a vector or query of length zero as 0.
method : public : Search(query:Float[], k:Int) ~ Vector<VectorHit>Parameters
| Name | Type | Description |
|---|---|---|
| query | Float | vector of exactly the index's dimension |
| k | Int | how many results to return |
Return
| Type | Description |
|---|---|
| Vector<VectorHit> | hits, closest first; empty, never Nil |
Store #
Writes the index to a file: a 12-byte header (the tag OVIX, a format byte, three reserved zero bytes, a CRC32 of the body), then the body (dimension, metric, count, and each id with its vector) through System.IO.Serializer.
method : public : Store(filename:String) ~ BoolParameters
| Name | Type | Description |
|---|---|---|
| filename | String | file to write |
Return
| Type | Description |
|---|---|
| Bool | true if written, false if the index is invalid or the file cannot be written |