Flat Index

Main Flat Class

template<data::ImmutableMemoryDataset Data, typename Dist, typename Ownership = OwnsMembers> class FlatIndex

Implementation of the Flat index.

The mid-level implementation for the flat index that uses exhaustive search to find the exact nearest neighbors (within the limitations of possibly quantization error for the dataset or floating-point error for some distance functors).

NOTE: This method is not as performant as other index methods. It is meant to return the exact rather than approximate nearest neighbors and thus must exhaustively search the whole dataset.

Template Parameters:

Data – The full type of the dataset being indexed.
Dist – The distance functor used to compare queries with the elements of the dataset.
Ownership – Implementation detail and may be ommitted for most use cases.

Public Types

using distance_type = Dist : The type of the distance functor.

using data_type = Data : The type of dataset.

Public Functions

template<typename ThreadPoolProto> inline FlatIndex(Data data, Dist distance, ThreadPoolProto &&threadpool_proto) requires std

Construct a new index from constituent parts.

Template Parameters:

ThreadPoolProto – The type of the threadpool proto type. See notes on the corresponding parameter below.

Parameters:

data – The data to use for the index. The resulting index will take ownership of the passed argument.
distance – The distance functor to use to compare queries with dataset elements.
threadpool_proto – Something that can be used to build a threadpool using threads::as_threadpool. In practice, this means that threapool_proto can be either a threadpool directly, or an integer. In the latter case, a new threadpool will be constructed using threadpool_proto as the number of threads to create.

inline size_t size() const: Return the number of independent entries in the index.

inline size_t dimensions() const: Return the logical number of dimensions of the indexed vectors.

template<typename QueryType, typename Pred = lib::Returns<lib::Const<true>>> inline void search(QueryResultView<size_t> result, const data::ConstSimpleDataView<QueryType> &queries, const search_parameters_type &search_parameters, Pred predicate = lib::Returns(lib::Const<true>()))

Fill the result with the num_neighbors nearest neighbors for each query.

Preconditions:

The following pre-conditions must hold. Otherwise, the behavior is undefined.

result.n_queries() == queries.size()
result.n_neighbors() == num_neighbors.
The value type of queries is compatible with the value type of the index dataset with respect to the stored distance functor.

Implementation Details

The internal call stack looks something like this.

search: Prepare scratch space and perform tiling over the dataset.
  |
  +-> search_subset: multi-threaded search of all queries over the current subset
      of the dataset. Partitions up the queries according to query batch size
      and dynamically load balances query partition among worker threads.
        |
        +-> search_patch: Bottom level routine meant to run on a single thread.
            Compute the distances between a subset of the queries and a subset
            of the data and maintines the `num_neighbors` best results seen so far.

{}

Template Parameters:

Queries – The full type of the queries.
Pred – The type of the optional predicate.

Parameters:

queries – The queries. Each entry will be processed.
num_neighbors – The number of approximate nearest neighbors to return for each query.
result – The result data structure to populate. Row i in the result corresponds to the neighbors for the ith query. Neighbors within each row are ordered from nearest to furthest.
predicate – A predicate functor that can be used to exclude certain dataset elements from consideration. This functor must implement bool operator()(size_t) where the size_t argument is an index in [0, data.size()). If the predicate returns true, that dataset element will be considered.

inline size_t get_num_threads() const

Return the current number of threads used for search.

Flat Entry Point

template<typename DataProto, typename Distance, typename ThreadPoolProto> auto svs::index::flat::auto_assemble(DataProto &&data_proto, Distance distance, ThreadPoolProto threadpool_proto)

Entry point for loading a Flat index.

This method provides much of the heavy lifting for constructing a Flat index from a data file on disk or a dataset in memory.

data_loader

The data loader should be any object loadable via svs::detail::dispatch_load returning a Vamana compatible dataset. Concrete examples include:

An instance of VectorDataLoader.
An LVQ loader: svs::quantization::lvq::LVQLoader.
An implementation of svs::data::ImmutableMemoryDataset (passed by value).

Parameters:

data_proto – Data prototype. See expanded notes.
distance – The distance functor to use to compare queries with elements of the dataset.
threadpool_proto – Precursor for the thread pool to use. Can either be a threadpool instance of an integer specifying the number of threads to use.