API Reference#

usearch/index.hpp#

Single-header Vector Search engine.

Author

Ash Vardanian

Date

April 26, 2023

Defines

USEARCH_VERSION_MAJOR#
USEARCH_VERSION_MINOR#
USEARCH_VERSION_PATCH#
USEARCH_64BIT_ENV#
USEARCH_USE_OPENMP#
usearch_concat_helper_m(a, b)#
usearch_concat_m(a, b)#
usearch_stringify_helper_m(x)#
usearch_stringify_m(x)#
usearch_prefetch_m(ptr)#
usearch_profiled_m#
usearch_profile_name_m(name)#
usearch_pack_m#
usearch_align_m#
usearch_assert_m(must_be_true, message)#
usearch_noexcept_m#

Typedefs

using byte_t = char#
using bitset_t = bitset_gt<>#
template<typename metric_at, typename ...args_at>
using return_type_gt = typename std::result_of<metric_at(args_at...)>::type#

C++17 and newer version deprecate the std::result_of

using default_key_t = std::uint64_t#
using default_slot_t = std::uint32_t#
using default_distance_t = float#

Functions

static inline void __usearch_raise_runtime_error(char const *message)#

Helper function to simplify debugging - trace just one symbol - __usearch_raise_runtime_error. Assuming the extern C block, the name won’t be mangled.

template<std::size_t multiple_ak>
std::size_t divide_round_up(std::size_t num) noexcept#
inline std::size_t divide_round_up(std::size_t num, std::size_t denominator) noexcept#
inline std::size_t ceil2(std::size_t v) noexcept#
template<typename at>
void misaligned_store(void *ptr, at v) noexcept#

Simply dereferencing misaligned pointers can be dangerous.

template<typename at>
at misaligned_load(void *ptr) noexcept#

Simply dereferencing misaligned pointers can be dangerous.

template<typename at, typename other_at = at>
at exchange(at &obj, other_at &&new_value)#

The std::exchange alternative for C++11.

template<typename at, typename sfinae_at = at>
std::enable_if<std::is_pod<sfinae_at>::value>::type destroy_at(at*)#

The std::destroy_at alternative for C++11.

template<typename at, typename sfinae_at = at>
std::enable_if<!std::is_pod<sfinae_at>::value>::type destroy_at(at *obj)#
template<typename at, typename sfinae_at = at>
std::enable_if<std::is_pod<sfinae_at>::value>::type construct_at(at*)#

The std::construct_at alternative for C++11.

template<typename at, typename sfinae_at = at>
std::enable_if<!std::is_pod<sfinae_at>::value>::type construct_at(at *obj)#
template<typename element_at>
element_at default_free_value()#
constexpr std::size_t default_connectivity()#

Number of neighbors per graph node. Defaults to 32 in FAISS and 16 in hnswlib.

It is called M in the paper.

constexpr std::size_t default_expansion_add()#

Hyper-parameter controlling the quality of indexing. Defaults to 40 in FAISS and 200 in hnswlib.

It is called efConstruction in the paper.

constexpr std::size_t default_expansion_search()#

Hyper-parameter controlling the quality of search. Defaults to 16 in FAISS and 10 in hnswlib.

It is called ef in the paper.

constexpr std::size_t default_allocator_entry_bytes()#
template<typename object_at>
static constexpr bool is_dummy()#

Checks if the provided object has a dummy type, emulating an interface, but performing no real computation.

template<typename at>
constexpr bool has_reset()#

Checks if a certain class has a member function called reset.

template<typename key_at>
inline std::size_t get_slot(member_gt<key_at> const &m) noexcept#
template<typename key_at>
inline key_at get_key(member_gt<key_at> const &m) noexcept#
template<typename key_at>
inline std::size_t get_slot(member_cref_gt<key_at> const &m) noexcept#
template<typename key_at>
inline key_at get_key(member_cref_gt<key_at> const &m) noexcept#
template<typename key_at>
inline std::size_t get_slot(member_ref_gt<key_at> const &m) noexcept#
template<typename key_at>
inline key_at get_key(member_ref_gt<key_at> const &m) noexcept#
template<typename men_at, typename women_at, typename men_values_at, typename women_values_at, typename men_metric_at, typename women_metric_at, typename man_to_woman_at = dummy_key_to_key_mapping_t, typename woman_to_man_at = dummy_key_to_key_mapping_t, typename executor_at = dummy_executor_t, typename progress_at = dummy_progress_t>
static join_result_t join(men_at const &men, women_at const &women, men_values_at const &men_values, women_values_at const &women_values, men_metric_at &&men_metric, women_metric_at &&women_metric, index_join_config_t config = {}, man_to_woman_at &&man_to_woman = man_to_woman_at{}, woman_to_man_at &&woman_to_man = woman_to_man_at{}, executor_at &&executor = executor_at{}, progress_at &&progress = progress_at{}) noexcept#

Adapts the Male-Optimal Stable Marriage algorithm for unequal sets to perform fast one-to-one matching between two large collections of vectors, using approximate nearest neighbors search.

Parameters:
  • man_to_woman[inout] Container to map ::men keys to ::women.

  • woman_to_man[inout] Container to map ::women keys to ::men.

  • executor[in] Thread-pool to execute the job in parallel.

  • progress[in] Callback to report the execution progress.

namespace unum#
namespace usearch#

Typedefs

using byte_t = char#
using bitset_t = bitset_gt<>#
template<typename metric_at, typename ...args_at>
using return_type_gt = typename std::result_of<metric_at(args_at...)>::type#

C++17 and newer version deprecate the std::result_of

using default_key_t = std::uint64_t#
using default_slot_t = std::uint32_t#
using default_distance_t = float#

Functions

template<std::size_t multiple_ak>
std::size_t divide_round_up(std::size_t num) noexcept#
inline std::size_t divide_round_up(std::size_t num, std::size_t denominator) noexcept#
inline std::size_t ceil2(std::size_t v) noexcept#
template<typename at>
void misaligned_store(void *ptr, at v) noexcept#

Simply dereferencing misaligned pointers can be dangerous.

template<typename at>
at misaligned_load(void *ptr) noexcept#

Simply dereferencing misaligned pointers can be dangerous.

template<typename at, typename other_at = at>
at exchange(at &obj, other_at &&new_value)#

The std::exchange alternative for C++11.

template<typename at, typename sfinae_at = at>
std::enable_if<std::is_pod<sfinae_at>::value>::type destroy_at(at*)#

The std::destroy_at alternative for C++11.

template<typename at, typename sfinae_at = at>
std::enable_if<!std::is_pod<sfinae_at>::value>::type destroy_at(at *obj)#
template<typename at, typename sfinae_at = at>
std::enable_if<std::is_pod<sfinae_at>::value>::type construct_at(at*)#

The std::construct_at alternative for C++11.

template<typename at, typename sfinae_at = at>
std::enable_if<!std::is_pod<sfinae_at>::value>::type construct_at(at *obj)#
template<typename element_at>
element_at default_free_value()#
constexpr std::size_t default_connectivity()#

Number of neighbors per graph node. Defaults to 32 in FAISS and 16 in hnswlib.

It is called M in the paper.

constexpr std::size_t default_expansion_add()#

Hyper-parameter controlling the quality of indexing. Defaults to 40 in FAISS and 200 in hnswlib.

It is called efConstruction in the paper.

constexpr std::size_t default_expansion_search()#

Hyper-parameter controlling the quality of search. Defaults to 16 in FAISS and 10 in hnswlib.

It is called ef in the paper.

constexpr std::size_t default_allocator_entry_bytes()#
template<typename object_at>
static constexpr bool is_dummy()#

Checks if the provided object has a dummy type, emulating an interface, but performing no real computation.

template<typename at>
constexpr bool has_reset()#

Checks if a certain class has a member function called reset.

template<typename key_at>
inline std::size_t get_slot(member_gt<key_at> const &m) noexcept#
template<typename key_at>
inline key_at get_key(member_gt<key_at> const &m) noexcept#
template<typename key_at>
inline std::size_t get_slot(member_cref_gt<key_at> const &m) noexcept#
template<typename key_at>
inline key_at get_key(member_cref_gt<key_at> const &m) noexcept#
template<typename key_at>
inline std::size_t get_slot(member_ref_gt<key_at> const &m) noexcept#
template<typename key_at>
inline key_at get_key(member_ref_gt<key_at> const &m) noexcept#
template<typename men_at, typename women_at, typename men_values_at, typename women_values_at, typename men_metric_at, typename women_metric_at, typename man_to_woman_at = dummy_key_to_key_mapping_t, typename woman_to_man_at = dummy_key_to_key_mapping_t, typename executor_at = dummy_executor_t, typename progress_at = dummy_progress_t>
static join_result_t join(men_at const &men, women_at const &women, men_values_at const &men_values, women_values_at const &women_values, men_metric_at &&men_metric, women_metric_at &&women_metric, index_join_config_t config = {}, man_to_woman_at &&man_to_woman = man_to_woman_at{}, woman_to_man_at &&woman_to_man = woman_to_man_at{}, executor_at &&executor = executor_at{}, progress_at &&progress = progress_at{}) noexcept#

Adapts the Male-Optimal Stable Marriage algorithm for unequal sets to perform fast one-to-one matching between two large collections of vectors, using approximate nearest neighbors search.

Parameters:
  • man_to_woman[inout] Container to map ::men keys to ::women.

  • woman_to_man[inout] Container to map ::women keys to ::men.

  • executor[in] Thread-pool to execute the job in parallel.

  • progress[in] Callback to report the execution progress.

template<typename at>
class misaligned_ref_gt#
#include <index.hpp>

A reference to a misaligned memory location with a specific type. It is needed to avoid Undefined Behavior when dereferencing addresses indivisible by sizeof(at).

Public Functions

inline misaligned_ref_gt(byte_t *ptr) noexcept#
inline operator mutable_t() const noexcept#
inline misaligned_ref_gt &operator=(mutable_t const &v) noexcept#
inline void reset(byte_t *ptr) noexcept#
inline byte_t *ptr() const noexcept#

Private Types

using element_t = at#
using mutable_t = typename std::remove_const<element_t>::type#

Private Members

byte_t *ptr_#
template<typename at>
class misaligned_ptr_gt#
#include <index.hpp>

A pointer to a misaligned memory location with a specific type. It is needed to avoid Undefined Behavior when dereferencing addresses indivisible by sizeof(at).

Public Types

using iterator_category = std::random_access_iterator_tag#
using value_type = element_t#
using difference_type = std::ptrdiff_t#
using pointer = misaligned_ptr_gt<element_t>#
using reference = misaligned_ref_gt<element_t>#

Public Functions

inline misaligned_ptr_gt(byte_t *ptr) noexcept#
inline reference operator*() const noexcept#
inline reference operator[](std::size_t i) noexcept#
inline value_type operator[](std::size_t i) const noexcept#
inline misaligned_ptr_gt &operator++() noexcept#
inline misaligned_ptr_gt &operator--() noexcept#
inline misaligned_ptr_gt operator++(int) noexcept#
inline misaligned_ptr_gt operator--(int) noexcept#
inline misaligned_ptr_gt operator+(difference_type d) const noexcept#
inline misaligned_ptr_gt operator-(difference_type d) const noexcept#
inline difference_type operator-(const misaligned_ptr_gt &other) const noexcept#
inline misaligned_ptr_gt &operator+=(difference_type d) noexcept#
inline misaligned_ptr_gt &operator-=(difference_type d) noexcept#
inline bool operator==(misaligned_ptr_gt const &other) const noexcept#
inline bool operator!=(misaligned_ptr_gt const &other) const noexcept#
inline bool operator<(misaligned_ptr_gt const &other) const noexcept#
inline bool operator<=(misaligned_ptr_gt const &other) const noexcept#
inline bool operator>(misaligned_ptr_gt const &other) const noexcept#
inline bool operator>=(misaligned_ptr_gt const &other) const noexcept#

Private Types

using element_t = at#
using mutable_t = typename std::remove_const<element_t>::type#

Private Members

byte_t *ptr_#
template<typename scalar_at>
class span_gt#
#include <index.hpp>

Non-owning memory range view, similar to std::span, but for C++11.

Public Functions

inline span_gt() noexcept#
inline span_gt(scalar_at *begin, scalar_at *end) noexcept#
inline span_gt(scalar_at *begin, std::size_t size) noexcept#
inline scalar_at *data() const noexcept#
inline std::size_t size() const noexcept#
inline scalar_at *begin() const noexcept#
inline scalar_at *end() const noexcept#
inline operator scalar_at*() const noexcept#

Private Members

scalar_at *data_#
std::size_t size_#
template<typename scalar_at, typename allocator_at = std::allocator<scalar_at>>
class buffer_gt#
#include <index.hpp>

Similar to std::vector, but doesn’t support dynamic resizing. On the bright side, this can’t throw exceptions.

Public Functions

inline buffer_gt() noexcept#
inline buffer_gt(std::size_t size) noexcept#
inline ~buffer_gt() noexcept#
inline void reset() noexcept#
inline scalar_at *data() const noexcept#
inline std::size_t size() const noexcept#
inline scalar_at *begin() const noexcept#
inline scalar_at *end() const noexcept#
inline operator scalar_at*() const noexcept#
inline scalar_at &operator[](std::size_t i) noexcept#
inline scalar_at const &operator[](std::size_t i) const noexcept#
inline explicit operator bool() const noexcept#
inline scalar_at *release() noexcept#
buffer_gt(buffer_gt const&) = delete#
buffer_gt &operator=(buffer_gt const&) = delete#
inline buffer_gt(buffer_gt &&other) noexcept#
inline buffer_gt &operator=(buffer_gt &&other) noexcept#

Private Members

scalar_at *data_#
std::size_t size_#
class error_t#
#include <index.hpp>

A lightweight error class for handling error messages, which are expected to be allocated in static memory.

Public Functions

inline error_t() noexcept#
inline error_t(char const *message) noexcept#
inline error_t &operator=(char const *message) noexcept#
error_t(error_t const&) = delete#
error_t &operator=(error_t const&) = delete#
inline error_t(error_t &&other) noexcept#
inline error_t &operator=(error_t &&other) noexcept#
inline explicit operator bool() const noexcept#

Checks if there was an error.

inline char const *what() const noexcept#

Returns the error message.

inline char const *release() noexcept#

Releases the error message, meaning the caller takes ownership.

inline ~error_t() noexcept#

Destructor terminates if an error was recorded.

inline void raise() noexcept#

Terminates if an error was recorded.

Private Members

char const *message_ = {}#
template<typename result_at>
struct expected_gt#
#include <index.hpp>

Similar to std::expected in C++23, wraps a statement evaluation result, or an error. It’s used to avoid raising exception, and gracefully propagate the error.

Template Parameters:

result_at – The type of the expected result.

Public Functions

inline operator result_at&() &#
inline operator result_at&&() &&#
inline result_at const &operator*() const noexcept#
inline explicit operator bool() const noexcept#
inline expected_gt failed(error_t message) noexcept#

Public Members

result_at result#
error_t error#
template<typename allocator_at = std::allocator<byte_t>>
class bitset_gt#
#include <index.hpp>

Light-weight bitset implementation to sync nodes updates during graph mutations. Extends basic functionality with atomic operations.

Public Functions

inline bitset_gt() noexcept#
inline ~bitset_gt() noexcept#
inline explicit operator bool() const noexcept#
inline void clear() noexcept#
inline void reset() noexcept#
inline bitset_gt(std::size_t capacity) noexcept#
inline bitset_gt(bitset_gt &&other) noexcept#
inline bitset_gt &operator=(bitset_gt &&other) noexcept#
bitset_gt(bitset_gt const&) = delete#
bitset_gt &operator=(bitset_gt const&) = delete#
inline bool test(std::size_t i) const noexcept#
inline bool set(std::size_t i) noexcept#
inline bool atomic_set(std::size_t i) noexcept#
inline void atomic_reset(std::size_t i) noexcept#
inline lock_t lock(std::size_t i) noexcept#

Private Types

using allocator_t = allocator_at#
using byte_t = typename allocator_t::value_type#
using compressed_slot_t = unsigned long#

Private Members

compressed_slot_t *slots_ = {}#
std::size_t count_ = {}#

Number of slots.

Private Static Functions

static inline constexpr std::size_t bits_per_slot()#
static inline constexpr compressed_slot_t bits_mask()#
static inline constexpr std::size_t slots(std::size_t bits)#
class lock_t#
#include <index.hpp>

Public Functions

inline ~lock_t() noexcept#
inline lock_t(bitset_gt &bitset, std::size_t bit_offset) noexcept#

Private Members

bitset_gt &bitset_#
std::size_t bit_offset_#
template<typename element_at, typename comparator_at = std::less<void>, typename allocator_at = std::allocator<element_at>>
class max_heap_gt#
#include <index.hpp>

Similar to std::priority_queue, but allows raw access to underlying memory, in case you want to shuffle it or sort. Good for collections from 100s to 10’000s elements.

In a max-heap, the heap property ensures that the value of each node is greater than or equal to the values of its children. This means that the largest element is always at the root of the heap.

Structures#

There are several designs of heaps. Binary heaps are the simplest & most common variant, that is easy to implement as a succint array. However, they are not the most efficient for all operations. Most importantly, melding (merging) of two heaps has linear complexity in time.

+————–&#8212;+——&#8212;+——–&#8212;+——&#8212;+———–&#8212;+——&#8212;+ | Operation | find-max| delete-max| insert | increase-key | meld | +————–&#8212;+——&#8212;+——–&#8212;+——&#8212;+———–&#8212;+——&#8212;+ | Binary | Θ(1) | Θ(log n) | O(log n)| O(log n) | Θ(n) | | Leftist | Θ(1) | Θ(log n) | O(log n)| Θ(log n) | Θ(log n)| | Binomial | Θ(1) | Θ(log n) | Θ(1) | Θ(log n) | O(log n)| | Skew binomial | Θ(1) | Θ(log n) | Θ(1) | O(log n) | O(log n)| | Pairing | Θ(1) | O(log n) | Θ(1) | o(log n) | Θ(1) | | Rank-pairing | Θ(1) | O(log n) | Θ(1) | Θ(1) | Θ(1) | | Fibonacci | Θ(1) | O(log n) | Θ(1) | Θ(1) | Θ(1) | | Strict Fibonacci| Θ(1) | O(log n) | Θ(1) | Θ(1) | Θ(1) | | Brodal | Θ(1) | Θ(log n) | Θ(1) | Θ(1) | Θ(1) | | 2–3 heap | Θ(1) | O(log n) | Θ(1) | Θ(1) | O(log n)| +————–&#8212;+——&#8212;+——–&#8212;+——&#8212;+———–&#8212;+——&#8212;+

It’s well known, that improved priority queue structures translate into better graph-transversal algorithms. For example, Dijkstra’s algorithm can be sped up by using a Fibonacci heap for arbitrary weights. For integer weight bounded by L, Schrijver reported following time complexities in 2004:

+———&#8212;+———————————-&#8212;+————————-&#8212;+———————–&#8212;+ | Weights | Algorithm | Time complexity | Author | +———&#8212;+———————————-&#8212;+————————-&#8212;+———————–&#8212;+ | R | | O(V^2 EL) | Ford 1956 | | R | Bellman–Ford algorithm | O(VE) | Shimbel 1955, Bellman | | | | | 1958, Moore 1959 | | R | | O(V^2 log V) | Dantzig 1960 | | R | Dijkstra’s with list | O(V^2) | Leyzorek et al. 1957, | | | | | Dijkstra 1959… | | R | Dijkstra’s with binary heap | O((E + V) log V) | Johnson 1977 | | R | Dijkstra’s with Fibonacci heap | O(E + V log V) | Fredman & Tarjan 1984, | | | | | Fredman & Tarjan 1987 | | R | Quantum Dijkstra | O(√VE log^2 V) | Dürr et al. 2006 | | R | Dial’s algorithm (Dijkstra’s using | O(E + LV) | Dial 1969 | | | a bucket queue with L buckets) | | | | N | | O(E log log L) | Johnson 1981, Karlsson & | | | | | Poblete 1983 | | N | Gabow’s algorithm | O(E log_E/V L) | Gabow 1983, Gabow 1985 | | N | | O(E + V √log L) | Ahuja et al. 1990 | | N | Thorup | O(E + V log log V) | Thorup 2004 | +———&#8212;+———————————-&#8212;+————————-&#8212;+———————–&#8212;+

Possible improvements:

Public Types

using element_t = element_at#
using comparator_t = comparator_at#
using allocator_t = allocator_at#
using value_type = element_t#

Public Functions

inline max_heap_gt() noexcept#
inline max_heap_gt(max_heap_gt &&other) noexcept#
inline max_heap_gt &operator=(max_heap_gt &&other) noexcept#
max_heap_gt(max_heap_gt const&) = delete#
max_heap_gt &operator=(max_heap_gt const&) = delete#
inline ~max_heap_gt() noexcept#
inline void reset() noexcept#
inline bool empty() const noexcept#
inline std::size_t size() const noexcept#
inline std::size_t capacity() const noexcept#
inline element_t *data() noexcept#
inline element_t const *data() const noexcept#
inline void clear() noexcept#
inline void shrink(std::size_t n) noexcept#
inline element_t const &top() const noexcept#

Selects the largest element in the heap.

Returns:

Reference to the stored element.

inline void sort_ascending() noexcept#

Invalidates the “max-heap” property, transforming into ascending range.

inline usearch_profiled_m bool reserve (std::size_t new_capacity) noexcept

Ensures the heap has enough capacity for the specified number of elements.

Parameters:

new_capacity – The desired minimum capacity.

Returns:

True if the capacity was successfully increased, false otherwise.

inline bool insert(element_t &&element) noexcept#

Inserts an element into the heap.

Parameters:

element – The element to be inserted.

Returns:

True if the element was successfully inserted, false otherwise.

inline usearch_profiled_m void insert_reserved (element_t &&element) noexcept

Inserts an element into the heap without reserving additional space.

Parameters:

element – The element to be inserted.

inline bool insert_many(element_t const *elements) noexcept#

Inserts multiple elements into the heap.

Parameters:

elements – Pointer to the elements to be inserted.

Returns:

True if the elements were successfully inserted, false otherwise.

inline usearch_profiled_m element_t pop () noexcept

Private Functions

inline void shift_up(std::size_t i) noexcept#

Shifts an element up to maintain the heap property. This operation is called when a new element is added at the end of the heap. The element is moved up until the heap property is restored.

Parameters:

i – Index of the element to be shifted up.

inline void shift_down(std::size_t i) noexcept#

Shifts an element down to maintain the heap property. This operation is called when the root element is removed and the last element is moved to the root. The element is moved down until the heap property is restored.

Parameters:

i – Index of the element to be shifted down.

Private Members

element_t *elements_#
std::size_t size_#
std::size_t capacity_#

Private Static Functions

static inline std::size_t parent_idx(std::size_t i) noexcept#
static inline std::size_t left_child_idx(std::size_t i) noexcept#
static inline std::size_t right_child_idx(std::size_t i) noexcept#
static inline bool less(element_t const &a, element_t const &b) noexcept#
template<typename element_at, typename comparator_at = std::less<void>, typename allocator_at = std::allocator<element_at>>
class sorted_buffer_gt#
#include <index.hpp>

Similar to std::priority_queue, but allows raw access to underlying memory and always keeps the data sorted. Ideal for small collections under 128 elements.

Public Types

using element_t = element_at#
using comparator_t = comparator_at#
using allocator_t = allocator_at#
using value_type = element_t#

Public Functions

inline sorted_buffer_gt() noexcept#
inline sorted_buffer_gt(sorted_buffer_gt &&other) noexcept#
inline sorted_buffer_gt &operator=(sorted_buffer_gt &&other) noexcept#
sorted_buffer_gt(sorted_buffer_gt const&) = delete#
sorted_buffer_gt &operator=(sorted_buffer_gt const&) = delete#
inline ~sorted_buffer_gt() noexcept#
inline void reset() noexcept#
inline bool empty() const noexcept#
inline std::size_t size() const noexcept#
inline std::size_t capacity() const noexcept#
inline element_t const &top() const noexcept#
inline void clear() noexcept#
inline bool reserve(std::size_t new_capacity) noexcept#
inline void insert_reserved(element_t &&element) noexcept#
inline bool insert(element_t &&element, std::size_t limit) noexcept#
Returns:

true if the entry was added, false if it wasn’t relevant enough.

inline bool insert_sorted(element_t const *elements, std::size_t elements_count, std::size_t limit) noexcept#
inline element_t pop() noexcept#
inline void sort_ascending() noexcept#
inline void shrink(std::size_t n) noexcept#
inline element_t *data() noexcept#
inline element_t const *data() const noexcept#

Private Members

element_t *elements_#
std::size_t size_#
std::size_t capacity_#

Private Static Functions

static inline bool less(element_t const &a, element_t const &b) noexcept#
class uint40_t#
#include <index.hpp>

Five-byte integer type to address node clouds with over 4B entries.

Public Functions

inline uint40_t() noexcept#
inline uint40_t(std::uint32_t n) noexcept#
inline uint40_t(std::uint64_t n) noexcept#
uint40_t(uint40_t&&) = default#
uint40_t(uint40_t const&) = default#
uint40_t &operator=(uint40_t&&) = default#
uint40_t &operator=(uint40_t const&) = default#
inline operator std::size_t() const noexcept#
inline bool operator==(uint40_t const &other) const noexcept#
inline bool operator!=(uint40_t const &other) const noexcept#
inline bool operator>(uint40_t const &other) const noexcept#
inline bool operator<=(uint40_t const &other) const noexcept#
inline bool operator>=(uint40_t const &other) const noexcept#
inline bool operator<(uint40_t const &other) const noexcept#

Public Static Functions

static inline uint40_t max() noexcept#
static inline uint40_t min() noexcept#

Private Functions

inline uint40_t &broadcast(unsigned char c)#

Private Members

unsigned char octets[5]#
template<typename element_at>
struct default_free_value_gt#
#include <index.hpp>

Reflection-helper to get the default “unused” value for a given type. Needed to initialize hash-sets and bit-sets.

Public Static Functions

template<typename sfinae_element_at = element_at, typename std::enable_if<std::is_integral<sfinae_element_at>::value>::type* = nullptr>
static inline sfinae_element_at value() noexcept#
template<typename sfinae_element_at = element_at, typename std::enable_if<!std::is_integral<sfinae_element_at>::value>::type* = nullptr>
static inline sfinae_element_at value() noexcept#
template<>
struct default_free_value_gt<uint40_t>#
#include <index.hpp>

Public Static Functions

static inline uint40_t value() noexcept#
template<typename element_at>
struct hash_gt#
#include <index.hpp>

Adapter to allow definining arbitrary hash functions for keys and slots. It’s added, as overloading std::hash is not recommended by the standard.

Public Functions

inline std::size_t operator()(element_at const &element) const noexcept#
template<>
struct hash_gt<uint40_t>#
#include <index.hpp>

Public Functions

inline std::size_t operator()(uint40_t const &element) const noexcept#
template<typename element_at, typename hasher_at = hash_gt<element_at>, typename allocator_at = std::allocator<byte_t>>
class growing_hash_set_gt#
#include <index.hpp>

Minimalistic hash-set implementation to track visited nodes during graph traversal. In our primary usecase, its a sparse alternative to a bit-set.

It doesn’t support deletion of separate objects, but supports clear-ing all at once. It expects reserve to be called ahead of all insertions, so no resizes are needed. It also assumes 0xFF...FF slots to be unused, to simplify the design. It uses linear probing, the number of slots is always a power of two, and it uses linear-probing in case of bucket collisions.

Public Functions

inline growing_hash_set_gt() noexcept#
inline ~growing_hash_set_gt() noexcept#
inline explicit operator bool() const noexcept#
inline std::size_t size() const noexcept#
inline void clear() noexcept#
inline void reset() noexcept#
inline growing_hash_set_gt(std::size_t capacity) noexcept#
inline growing_hash_set_gt(growing_hash_set_gt &&other) noexcept#
inline growing_hash_set_gt &operator=(growing_hash_set_gt &&other) noexcept#
growing_hash_set_gt(growing_hash_set_gt const&) = delete#
growing_hash_set_gt &operator=(growing_hash_set_gt const&) = delete#
inline bool test(element_t const &elem) const noexcept#

Checks if the element is already in the hash-set.

Returns:

true if the element is already in the hash-set.

inline bool set(element_t const &elem) noexcept#

Inserts an element into the hash-set.

Returns:

Similar to bitset_gt, returns the previous value.

inline bool reserve(std::size_t new_capacity) noexcept#

Extends the capacity of the hash-set.

Returns:

true if enough capacity is available, false if memory allocation failed.

Private Types

using element_t = element_at#
using hasher_t = hasher_at#
using allocator_t = allocator_at#
using byte_t = typename allocator_t::value_type#

Private Members

element_t *slots_ = {}#
std::size_t capacity_ = {}#

Number of slots.

std::size_t count_ = {}#

Number of populated.

hasher_t hasher_ = {}#
template<typename element_at, typename allocator_at = std::allocator<element_at>>
class ring_gt#
#include <index.hpp>

Basic single-threaded ring class, used for all kinds of task queues.

Public Types

using element_t = element_at#
using allocator_t = allocator_at#
using value_type = element_t#

Public Functions

inline explicit ring_gt(allocator_t const &alloc = allocator_t()) noexcept#
ring_gt(ring_gt const&) = delete#
ring_gt &operator=(ring_gt const&) = delete#
inline ring_gt(ring_gt &&other) noexcept#
inline ring_gt &operator=(ring_gt &&other) noexcept#
inline void swap(ring_gt &other) noexcept#
inline ~ring_gt() noexcept#
inline bool empty() const noexcept#
inline size_t capacity() const noexcept#
inline size_t size() const noexcept#
inline void clear() noexcept#
inline void reset() noexcept#
inline bool reserve(std::size_t n) noexcept#
inline void push (element_t const &value) usearch_noexcept_m
inline bool try_push(element_t const &value) noexcept#
inline bool try_pop(element_t &value) noexcept#
inline element_t const &operator[](std::size_t i) const noexcept#

Private Members

element_t *elements_ = {}#
std::size_t capacity_ = {}#
std::size_t head_ = {}#
std::size_t tail_ = {}#
bool empty_ = {true}#
allocator_t allocator_ = {}#
struct index_config_t#
#include <index.hpp>

Configuration settings for the index construction. Includes the main ::connectivity parameter (M in the paper) and two expansion factors - for construction and search.

Subclassed by unum::usearch::index_dense_config_t

Public Functions

inline index_config_t() = default#
inline index_config_t(std::size_t c, std::size_t cb = 0) noexcept#
inline error_t validate() noexcept#

Validates the configuration settings, updating them in-place.

Returns:

Error message, if any.

inline bool is_valid() const noexcept#

Immutable function to check if the configuration is valid.

Returns:

true if the configuration is valid.

Public Members

std::size_t connectivity = default_connectivity()#

Number of neighbors per graph node. Defaults to 32 in FAISS and 16 in hnswlib.

It is called M in the paper.

std::size_t connectivity_base = default_connectivity() * 2#

Number of neighbors per graph node in base level graph. Defaults to double of the other levels, so 64 in FAISS and 32 in hnswlib.

It is called M0 in the paper.

struct index_limits_t#
#include <index.hpp>

Growth settings for the index container. Includes the upper bound for ::members capacity, and the number of read/write threads expected to work with the index.

Public Functions

inline index_limits_t(std::size_t n, std::size_t t) noexcept#
inline index_limits_t(std::size_t n = 0) noexcept#
inline std::size_t threads() const noexcept#

Returns the upper limit for the number of threads.

inline std::size_t concurrency() const noexcept#

Returns the concurrency-level of the index - the minimum of thread counts.

Public Members

std::size_t members = 0#

Maximum number of entries in the index.

std::size_t threads_add = std::thread::hardware_concurrency()#

Max number of threads simultaneously updating entries.

std::size_t threads_search = std::thread::hardware_concurrency()#

Max number of threads simultaneously searching entries.

struct index_update_config_t#
#include <index.hpp>

Public Members

std::size_t expansion = default_expansion_add()#

Hyper-parameter controlling the quality of indexing. Defaults to 40 in FAISS and 200 in hnswlib.

It is called efConstruction in the paper.

std::size_t thread = 0#

Optional thread identifier for multi-threaded construction.

struct index_search_config_t#
#include <index.hpp>

Public Members

std::size_t expansion = default_expansion_search()#

Hyper-parameter controlling the quality of search. Defaults to 16 in FAISS and 10 in hnswlib.

It is called ef in the paper.

std::size_t thread = 0#

Optional thread identifier for multi-threaded construction.

bool exact = false#

Brute-forces exhaustive search over all entries in the index.

struct index_cluster_config_t#
#include <index.hpp>

Public Members

std::size_t expansion = default_expansion_search()#

Hyper-parameter controlling the quality of search. Defaults to 16 in FAISS and 10 in hnswlib.

It is called ef in the paper.

std::size_t thread = 0#

Optional thread identifier for multi-threaded construction.

struct index_copy_config_t#
#include <index.hpp>

Subclassed by unum::usearch::index_dense_copy_config_t

struct index_join_config_t#
#include <index.hpp>

Public Members

std::size_t max_proposals = 0#

Controls maximum number of proposals per man during stable marriage.

std::size_t expansion = default_expansion_search()#

Hyper-parameter controlling the quality of search. Defaults to 16 in FAISS and 10 in hnswlib.

It is called ef in the paper.

bool exact = false#

Brute-forces exhaustive search over all entries in the index.

struct dummy_predicate_t#
#include <index.hpp>

An example of what a USearch-compatible ad-hoc filter would look like.

A similar function object can be passed to search queries to further filter entries on their auxiliary properties, such as some categorical keys stored in an external DBMS.

Public Functions

template<typename member_at>
inline constexpr bool operator()(member_at&&) const noexcept#
struct dummy_callback_t#
#include <index.hpp>

An example of what a USearch-compatible ad-hoc operation on in-flight entries.

This kind of callbacks is used when the engine is being updated and you want to patch the entries, while their are still under locks - limiting concurrent access and providing consistency.

Public Functions

template<typename member_at>
inline void operator()(member_at&&) const noexcept#
struct dummy_progress_t#
#include <index.hpp>

An example of what a USearch-compatible progress-bar should look like.

This is particularly helpful when handling long-running tasks, like serialization, saving, and loading from disk, or index-level joins. The reporter checks return value to continue or stop the process, false means need to stop.

Public Functions

inline bool operator()(std::size_t, std::size_t) const noexcept#
struct dummy_prefetch_t#
#include <index.hpp>

An example of what a USearch-compatible values prefetching mechanism should look like.

USearch is designed to handle very large datasets, that may not fir into RAM. Fetching from external memory is very expensive, so we’ve added a pre-fetching mechanism, that accepts multiple objects at once, to cache in RAM ahead of the computation. The received iterators support both get_slot and get_key operations. An example usage may look like this:

template <typename member_citerator_like_at>
inline void operator()(member_citerator_like_at, member_citerator_like_at) const noexcept {
    for (; begin != end; ++begin)
        io_uring_prefetch(offset_in_file(get_key(begin)));
}

Public Functions

template<typename member_citerator_like_at>
inline void operator()(member_citerator_like_at, member_citerator_like_at) const noexcept#
struct dummy_executor_t#
#include <index.hpp>

An example of what a USearch-compatible executor (thread-pool) should look like.

It’s expected to have parallel(callback) API to schedule one task per thread; an identical fixed(count, callback) and dynamic(count, callback) overloads that also accepts the number of tasks, and somehow schedules them between threads; as well as size() to determine the number of available threads.

Public Functions

inline dummy_executor_t() noexcept#
inline std::size_t size() const noexcept#
template<typename thread_aware_function_at>
inline void fixed(std::size_t tasks, thread_aware_function_at &&thread_aware_function) noexcept#
template<typename thread_aware_function_at>
inline void dynamic(std::size_t tasks, thread_aware_function_at &&thread_aware_function) noexcept#
template<typename thread_aware_function_at>
inline void parallel(thread_aware_function_at &&thread_aware_function) noexcept#
struct dummy_key_to_key_mapping_t#
#include <index.hpp>

An example of what a USearch-compatible key-to-key mapping should look like.

This is particularly helpful for “Semantic Joins”, where we map entries of one collection to entries of another. In asymmetric setups, where A -> B is needed, but B -> A is not, this can be passed to minimize memory usage.

Public Functions

template<typename key_at>
inline member_ref_t operator[](key_at&&) const noexcept#
struct member_ref_t#
#include <index.hpp>

Public Functions

template<typename key_at>
inline member_ref_t &operator=(key_at&&) noexcept#
template<typename, typename at>
struct has_reset_gt#
#include <index.hpp>
template<typename check_at, typename return_at, typename ...args_at>
struct has_reset_gt<check_at, return_at(args_at...)>#
#include <index.hpp>

Public Static Attributes

static constexpr bool value = type::value#

Private Members

decltype(check< check_at >(0)) typedef type

Private Static Functions

template<typename at>
static constexpr auto check(at*) -> typename std::is_same<decltype(std::declval<at>().reset(std::declval<args_at>()...)), return_at>::type#
template<typename>
static constexpr std::false_type check(...)#
struct serialization_result_t#
#include <index.hpp>

Public Functions

inline explicit operator bool() const noexcept#
inline serialization_result_t failed(error_t message) noexcept#

Public Members

error_t error#
class output_file_t#
#include <index.hpp>

Smart-pointer wrapping the LibC for binary file outputs.

This class raises no exceptions and corresponds errors through serialization_result_t. The class automatically closes the file when the object is destroyed.

Public Functions

inline output_file_t(char const *path) noexcept#
inline ~output_file_t() noexcept#
inline output_file_t(output_file_t &&other) noexcept#
inline output_file_t &operator=(output_file_t &&other) noexcept#
inline serialization_result_t open_if_not() noexcept#
inline serialization_result_t write(void const *begin, std::size_t length) noexcept#
inline void close() noexcept#

Private Members

char const *path_ = nullptr#
std::FILE *file_ = nullptr#
class input_file_t#
#include <index.hpp>

Smart-pointer wrapping the LibC for binary files inputs.

This class raises no exceptions and corresponds errors through serialization_result_t. The class automatically closes the file when the object is destroyed.

Public Functions

inline input_file_t(char const *path) noexcept#
inline ~input_file_t() noexcept#
inline input_file_t(input_file_t &&other) noexcept#
inline input_file_t &operator=(input_file_t &&other) noexcept#
inline serialization_result_t open_if_not() noexcept#
inline serialization_result_t read(void *begin, std::size_t length) noexcept#
inline void close() noexcept#
inline explicit operator bool() const noexcept#
inline bool seek_to(std::size_t progress) noexcept#
inline bool seek_to_end() noexcept#
inline bool infer_progress(std::size_t &progress) noexcept#

Private Members

char const *path_ = nullptr#
std::FILE *file_ = nullptr#
class memory_mapped_file_t#
#include <index.hpp>

Represents a memory-mapped file or a pre-allocated anonymous memory region.

This class provides a convenient way to memory-map a file and access its contents as a block of memory. The class handles platform-specific memory-mapping operations on Windows, Linux, and MacOS. The class automatically closes the file when the object is destroyed.

Public Functions

inline explicit operator bool() const noexcept#
inline byte_t *data() noexcept#
inline byte_t const *data() const noexcept#
inline std::size_t size() const noexcept#
inline memory_mapped_file_t() noexcept#
inline memory_mapped_file_t(char const *path) noexcept#
inline ~memory_mapped_file_t() noexcept#
inline memory_mapped_file_t(memory_mapped_file_t &&other) noexcept#
inline memory_mapped_file_t(byte_t *data, std::size_t length) noexcept#
inline memory_mapped_file_t &operator=(memory_mapped_file_t &&other) noexcept#
inline serialization_result_t open_if_not() noexcept#
inline void close() noexcept#

Private Members

char const *path_ = {}#

The path to the file to be memory-mapped.

void *ptr_ = {}#

A pointer to the memory-mapping.

size_t length_ = {}#

The length of the memory-mapped file in bytes.

int file_descriptor_ = {}#

The file descriptor on Linux and MacOS.

struct index_serialized_header_t#
#include <index.hpp>

Metadata header for the serialized index.

This structure is very minimalistic by design. It contains no information about the capacity of the index, so you’ll have to reserve after loading. It also contains no info on the metric or key types, so you’ll have to store that information elsewhere, like we do in index_dense_head_t.

Public Members

std::uint64_t size = 0#
std::uint64_t connectivity = 0#
std::uint64_t connectivity_base = 0#
std::uint64_t max_level = 0#
std::uint64_t entry_slot = 0#
template<typename key_at = default_key_t>
struct member_gt#
#include <index.hpp>

Public Members

key_at key#
std::size_t slot#
template<typename key_at = default_key_t>
struct member_cref_gt#
#include <index.hpp>

Public Members

misaligned_ref_gt<key_at const> key#
std::size_t slot#
template<typename key_at = default_key_t>
struct member_ref_gt#
#include <index.hpp>

Public Functions

inline operator member_cref_gt<key_at>() const noexcept#

Public Members

misaligned_ref_gt<key_at> key#
std::size_t slot#
template<typename distance_at = default_distance_t, typename key_at = default_key_t, typename compressed_slot_at = default_slot_t, typename dynamic_allocator_at = std::allocator<byte_t>, typename tape_allocator_at = dynamic_allocator_at>
class index_gt#
#include <index.hpp>

Approximate Nearest Neighbors Search index-structure using the Hierarchical Navigable Small World (HNSW) graphs algorithm. If classical containers store Key->Value mappings, this one can be seen as a network of keys, accelerating approximate Value~>Key visited_members.

Unlike most implementations, this one is generic anc can be used for any search, not just within equi-dimensional vectors. Examples range from Texts to similar Chess positions, Geo-Spatial Search, and even Graphs.

Features#

- Thread-safe for concurrent construction, search, and updates.
- Doesn't allocate new threads, and reuses the ones its called from.
- Allows storing value externally, managing just the similarity index.
- Joins.

Usage#

Exceptions#

None of the methods throw exceptions in the “Release” compilation mode. It may only throw if your memory ::dynamic_allocator_at or ::metric_at isn’t safe to copy.

Serialization#

When serialized, doesn’t include any additional metadata. It is just the multi-level proximity-graph. You may want to store metadata about the used metric and key types somewhere else.

Details#

Like every HNSW implementation, USearch builds levels of “Proximity Graphs”. Every added vector forms a node in one or more levels of the graph. Every node is present in the base level. Every following level contains a smaller fraction of nodes. During search, the operation starts with the smaller levels and zooms-in on every following iteration of larger graph traversals.

Just one memory allocation is performed regardless of the number of levels. The adjacency lists across all levels are concatenated into that single buffer. That buffer starts with a “head”, that stores the metadata, such as the tallest “level” of the graph that it belongs to, the external “key”, and the number of “dimensions” in the vector.

, Predicates and Callbacks#

References and Iterators#

-   `member_citerator_t` and `member_iterator_t` have only slots, no indirections.

-   `member_cref_t` and `member_ref_t` contains the `slot` and a reference
    to the key. So it passes through 1 level of visited_members in `nodes_`.
    Retrieving the key via `get_key` will cause fetching yet another cache line.

-   `member_gt` contains an already prefetched copy of the key.
Template Parameters:
  • key_at – The type of primary objects stored in the index. The values, to which those map, are not managed by the same index structure.

  • compressed_slot_at – The smallest unsigned integer type to address indexed elements. It is used internally to maximize space-efficiency and is generally up-casted to in public interfaces. Can be a built-in , uint64_t, or our custom . Which makes the most sense for 4B+ entry indexes.

  • dynamic_allocator_at – Dynamic memory allocator for temporary buffers, visits indicators, and priority queues, needed during construction and traversals of graphs. The allocated buffers may be uninitialized.

  • tape_allocator_at – Potentially different memory allocator for primary allocations of nodes and vectors. It would never deallocate separate entries, and would only free all the space at once. The allocated buffers may be uninitialized.

Public Types

using distance_t = distance_at#
using vector_key_t = key_at#
using key_t = vector_key_t#
using compressed_slot_t = compressed_slot_at#
using dynamic_allocator_t = dynamic_allocator_at#
using tape_allocator_t = tape_allocator_at#
using member_cref_t = member_cref_gt<vector_key_t>#
using member_ref_t = member_ref_gt<vector_key_t>#
using member_iterator_t = member_iterator_gt<member_ref_t, index_gt>#
using member_citerator_t = member_iterator_gt<member_cref_t, index_gt const>#
using value_type = vector_key_t#
using allocator_type = dynamic_allocator_t#
using size_type = std::size_t#
using difference_type = std::ptrdiff_t#
using reference = member_ref_t#
using const_reference = member_cref_t#
using pointer = void#
using const_pointer = void#
using iterator = member_iterator_t#
using const_iterator = member_citerator_t#
using reverse_iterator = std::reverse_iterator<member_iterator_t>#
using reverse_const_iterator = std::reverse_iterator<member_citerator_t>#
using dynamic_allocator_traits_t = std::allocator_traits<dynamic_allocator_t>#
using byte_t = typename dynamic_allocator_t::value_type#
using tape_allocator_traits_t = std::allocator_traits<tape_allocator_t>#
using copy_result_t = state_result_t#

Public Functions

inline std::size_t connectivity() const noexcept#
inline std::size_t capacity() const noexcept#
inline std::size_t size() const noexcept#
inline std::size_t max_level() const noexcept#
inline index_config_t const &config() const noexcept#
inline index_limits_t const &limits() const noexcept#
inline bool is_immutable() const noexcept#
inline explicit operator bool() const noexcept#
inline explicit index_gt(dynamic_allocator_t dynamic_allocator = {}, tape_allocator_t tape_allocator = {}) noexcept(false)#

Default index constructor, suitable only for stateless allocators.

Exceptions#

Doesn’t throw, unless the ::dynamic_allocator’s and ::tape_allocator’s throw on move-construction.

Warning

Consider index_gt::make instead, or explicitly convert to bool to check if the index is valid.

inline explicit index_gt(index_config_t config, dynamic_allocator_t dynamic_allocator = {}, tape_allocator_t tape_allocator = {}) noexcept(false)#

Default index constructor, suitable only for stateless allocators.

Exceptions#

Doesn’t throw, unless the ::dynamic_allocator’s and ::tape_allocator’s throw on move-construction.

Warning

Consider index_gt::make instead, or explicitly convert to bool to check if the index is valid.

inline index_gt fork() noexcept#

Clones the structure with the same hyper-parameters, but without contents.

inline ~index_gt() noexcept#
inline index_gt(index_gt &&other) noexcept#
inline index_gt &operator=(index_gt &&other) noexcept#
inline copy_result_t copy(index_copy_config_t config = {}) const noexcept#

The recommended way to copy the index, as unlike the copy-constructor, it can fail with an error message, without raising an exception.

Parameters:

config[in] The configuration specs for the copy-operation. Currently unused.

inline member_citerator_t cbegin() const noexcept#
inline member_citerator_t cend() const noexcept#
inline member_citerator_t begin() const noexcept#
inline member_citerator_t end() const noexcept#
inline member_iterator_t begin() noexcept#
inline member_iterator_t end() noexcept#
inline member_ref_t at(compressed_slot_t slot) noexcept#
inline member_cref_t at(compressed_slot_t slot) const noexcept#
inline member_iterator_t iterator_at(compressed_slot_t slot) noexcept#
inline member_citerator_t citerator_at(compressed_slot_t slot) const noexcept#
inline dynamic_allocator_t const &dynamic_allocator() const noexcept#
inline tape_allocator_t const &tape_allocator() const noexcept#
inline void clear() noexcept#

Erases all the vectors from the index.

Will change size() to zero, but will keep the same capacity(). Will keep the number of available threads/contexts the same as it was.

inline void reset() noexcept#

Erases all members from index, closing files, and returning RAM to OS.

Will change both size() and capacity() to zero. Will deallocate all threads/contexts. If the index is memory-mapped - releases the mapping and the descriptor.

inline void swap(index_gt &other) noexcept#

Swaps the underlying memory buffers and thread contexts.

inline bool try_reserve (index_limits_t limits) usearch_noexcept_m

Increases the capacity() of the index to allow adding more vectors.

Returns:

true on success, false on memory allocation errors.

inline bool reserve (index_limits_t limits) usearch_noexcept_m

Increases the capacity() of the index to allow adding more vectors.

Warning

Unlike STL, won’t throw exceptions on memory allocations, so check the return value.

Returns:

true on success, false on memory allocation errors.

template<typename value_at, typename metric_at, typename callback_at = dummy_callback_t, typename prefetch_at = dummy_prefetch_t> inline add_result_t add (vector_key_t key, value_at &&value, metric_at &&metric, index_update_config_t config={}, callback_at &&callback=callback_at{}, prefetch_at &&prefetch=prefetch_at{}) usearch_noexcept_m

Inserts a new entry into the index. Thread-safe. Supports heterogeneous lookups. Expects needed capacity to be reserved ahead of time: size() < capacity().

Template Parameters:

metric_at – A function responsible for computing the distance (dis-similarity) between two objects. It should be callable into distinctly different scenarios:

  • distance_t operator() (value_at, entry_at) - from new object to existing entries.

  • distance_t operator() (entry_at, entry_at) - between existing entries. Where any possible entry_at has both two interfaces: std::size_t slot(), vector_key_t key().

Parameters:
  • key[in] External identifier/name/descriptor for the new entry.

  • value[in] Content that will be compared against other entries to index.

  • metric[in] Callable object measuring distance between ::value and present objects.

  • config[in] Configuration options for this specific operation.

  • callback[in] On-success callback, executed while the member_ref_t is still under lock.

template<typename value_at, typename metric_at, typename callback_at = dummy_callback_t, typename prefetch_at = dummy_prefetch_t> inline add_result_t update (member_iterator_t iterator, vector_key_t key, value_at &&value, metric_at &&metric, index_update_config_t config={}, callback_at &&callback=callback_at{}, prefetch_at &&prefetch=prefetch_at{}) usearch_noexcept_m

Update an existing entry. Thread-safe. Supports heterogeneous lookups.

! It’s assumed that different threads aren’t updating the same entry at the same time. ! The state won’t be corrupted, but no transactional guarantees are provided and the ! resulting value & neighbors list may be inconsistent.

Template Parameters:

metric_at – A function responsible for computing the distance (dis-similarity) between two objects. It should be callable into distinctly different scenarios:

  • distance_t operator() (value_at, entry_at) - from new object to existing entries.

  • distance_t operator() (entry_at, entry_at) - between existing entries. For any possible entry_at following interfaces will work:

  • std::size_t get_slot(entry_at const &)

  • vector_key_t get_key(entry_at const &)

Parameters:
  • iterator[in] Iterator pointing to an existing entry to be replaced.

  • key[in] External identifier/name/descriptor for the entry.

  • value[in] Content that will be compared against other entries in the index.

  • metric[in] Callable object measuring distance between ::value and present objects.

  • config[in] Configuration options for this specific operation.

  • callback[in] On-success callback, executed while the member_ref_t is still under lock.

template<typename value_at, typename metric_at, typename predicate_at = dummy_predicate_t, typename prefetch_at = dummy_prefetch_t> inline search_result_t search (value_at &&query, std::size_t wanted, metric_at &&metric, index_search_config_t config={}, predicate_at &&predicate=predicate_at{}, prefetch_at &&prefetch=prefetch_at{}) const usearch_noexcept_m

Searches for the closest elements to the given ::query. Thread-safe.

Parameters:
  • query[in] Content that will be compared against other entries in the index.

  • wanted[in] The upper bound for the number of results to return.

  • config[in] Configuration options for this specific operation.

  • predicate[in] Optional filtering predicate for member_cref_t.

Returns:

Smart object referencing temporary memory. Valid until next search(), add(), or cluster().

template<typename value_at, typename metric_at, typename predicate_at = dummy_predicate_t, typename prefetch_at = dummy_prefetch_t>
inline cluster_result_t cluster(value_at &&query, std::size_t level, metric_at &&metric, index_cluster_config_t config = {}, predicate_at &&predicate = predicate_at{}, prefetch_at &&prefetch = prefetch_at{}) const noexcept#

Identifies the closest cluster to the given ::query. Thread-safe.

Parameters:
  • query[in] Content that will be compared against other entries in the index.

  • level[in] The index level to target. Higher means lower resolution.

  • config[in] Configuration options for this specific operation.

  • predicate[in] Optional filtering predicate for member_cref_t.

Returns:

Smart object referencing temporary memory. Valid until next search(), add(), or cluster().

inline stats_t stats() const noexcept#

Aggregates stats on the number of nodes, edges, and memory usage across all levels.

inline stats_t stats(std::size_t level) const noexcept#

Aggregates stats on the number of nodes, edges, and memory usage up to a specific level.

The level parameter is zero-based, where 0 is the base level. For example, level=1 will include the base level and the first level of connections.

inline stats_t stats(stats_t *stats_per_level, std::size_t max_level) const noexcept#

Aggregates stats on the number of nodes, edges, and memory usage up to a specific level, simultaneously exporting the stats for each level into the stats_per_level C-style array.

The max_level parameter is zero-based, where 0 is the base level. For example, max_level=1 will include the base level and the first level of connections.

inline std::size_t memory_usage(std::size_t allocator_entry_bytes = default_allocator_entry_bytes()) const noexcept#

A relatively accurate lower bound on the amount of memory consumed by the system. In practice it’s error will be below 10%.

See also

serialized_length for the length of the binary serialized representation.

inline std::size_t memory_usage_per_node(level_t level) const noexcept#
inline std::size_t serialized_length() const noexcept#

Estimate the binary length (in bytes) of the serialized index.

template<typename output_callback_at, typename progress_at = dummy_progress_t>
inline serialization_result_t save_to_stream(output_callback_at &&output, progress_at &&progress = {}) const noexcept#

Saves serialized binary index representation to a stream.

template<typename input_callback_at, typename progress_at = dummy_progress_t>
inline serialization_result_t load_from_stream(input_callback_at &&input, progress_at &&progress = {}) noexcept#

Symmetric to save_from_stream, pulls data from a stream.

template<typename progress_at = dummy_progress_t>
inline serialization_result_t save(char const *file_path, progress_at &&progress = {}) const noexcept#
template<typename progress_at = dummy_progress_t>
inline serialization_result_t load(char const *file_path, progress_at &&progress = {}) noexcept#
template<typename progress_at = dummy_progress_t>
inline serialization_result_t save(output_file_t file, progress_at &&progress = {}) const noexcept#

Saves serialized binary index representation to a file, generally on disk.

template<typename progress_at = dummy_progress_t>
inline serialization_result_t save(memory_mapped_file_t file, std::size_t offset = 0, progress_at &&progress = {}) const noexcept#

Memory-maps the serialized binary index representation from disk, without copying data into RAM, and fetching it on-demand.

template<typename progress_at = dummy_progress_t>
inline serialization_result_t load(input_file_t file, progress_at &&progress = {}) noexcept#

Loads the serialized binary index representation from disk to RAM. Adjusts the configuration properties of the constructed index to match the settings in the file.

template<typename progress_at = dummy_progress_t>
inline serialization_result_t load(memory_mapped_file_t file, std::size_t offset = 0, progress_at &&progress = {}) noexcept#

Loads the serialized binary index representation from disk to RAM. Adjusts the configuration properties of the constructed index to match the settings in the file.

template<typename progress_at = dummy_progress_t>
inline serialization_result_t view(memory_mapped_file_t file, std::size_t offset = 0, progress_at &&progress = {}) noexcept#

Memory-maps the serialized binary index representation from disk, without copying data into RAM, and fetching it on-demand.

template<typename values_at, typename metric_at, typename slot_transition_at = dummy_key_to_key_mapping_t, typename executor_at = dummy_executor_t, typename progress_at = dummy_progress_t, typename prefetch_at = dummy_prefetch_t>
inline void compact(values_at &&values, metric_at &&metric, slot_transition_at &&slot_transition, executor_at &&executor = executor_at{}, progress_at &&progress = progress_at{}, prefetch_at &&prefetch = prefetch_at{}) noexcept#

Performs compaction on the whole HNSW index, purging some entries and links to them, while also generating a more efficient mapping, putting the more frequently used entries closer together.

Parameters:
  • values[in] A []-subscriptable object, providing access to the values.

  • metric[in] Callable object measuring distance between any ::values and present objects.

  • slot_transition[in] Callable object to inform changes in slot assignments.

  • executor[in] Thread-pool to execute the job in parallel.

  • progress[in] Callback to report the execution progress.

  • prefetch[in] Callable object to prefetch data into the cache.

template<typename allow_member_at = dummy_predicate_t, typename executor_at = dummy_executor_t, typename progress_at = dummy_progress_t>
inline void isolate(allow_member_at &&allow_member, executor_at &&executor = executor_at{}, progress_at &&progress = progress_at{}) noexcept#

Scans the whole collection, removing the links leading towards banned entries. This essentially isolates some nodes from the rest of the graph, while keeping their outgoing links, in case the node is structurally relevant and has a crucial role in the index. It won’t reclaim the memory.

Parameters:
  • allow_member[in] Predicate to mark nodes for isolation.

  • executor[in] Thread-pool to execute the job in parallel.

  • progress[in] Callback to report the execution progress.

Public Static Functions

static inline state_result_t make(index_config_t config = {}, dynamic_allocator_t dynamic_allocator = {}, tape_allocator_t tape_allocator = {}) noexcept#

The recommended way to initialize the index, as unlike the constructor, it can fail with an error message, without raising an exception.

Parameters:
  • config[in] The configuration specs of the index.

  • dynamic_allocator[in] The allocator for temporary buffers and thread contexts, like priority queues.

  • tape_allocator[in] The allocator for the primary allocations of nodes and vectors.

Private Types

using neighbors_count_t = std::uint32_t#

Integer for the number of node neighbors at a specific level of the multi-level graph. It’s selected to be std::uint32_t to improve the alignment in most common cases.

using level_t = std::int16_t#
using nodes_mutexes_t = bitset_gt<dynamic_allocator_t>#
using visits_hash_set_t = growing_hash_set_gt<compressed_slot_t, hash_gt<compressed_slot_t>, dynamic_allocator_t>#
using candidates_view_t = span_gt<candidate_t const>#
using candidates_allocator_t = typename dynamic_allocator_traits_t::template rebind_alloc<candidate_t>#
using top_candidates_t = sorted_buffer_gt<candidate_t, std::less<candidate_t>, candidates_allocator_t>#
using next_candidates_t = max_heap_gt<candidate_t, std::less<candidate_t>, candidates_allocator_t>#
using nodes_allocator_t = typename dynamic_allocator_traits_t::template rebind_alloc<node_t>#
using contexts_allocator_t = typename dynamic_allocator_traits_t::template rebind_alloc<context_t>#
using span_bytes_t = span_gt<byte_t>#

Private Functions

inline span_bytes_t node_bytes_(node_t node) const noexcept#
inline std::size_t node_bytes_(level_t level) const noexcept#
inline std::size_t node_neighbors_bytes_(node_t node) const noexcept#
inline std::size_t node_neighbors_bytes_(level_t level) const noexcept#
inline span_bytes_t node_malloc_(level_t level) noexcept#
inline node_t node_make_(vector_key_t key, level_t level) noexcept#
inline node_t node_make_copy_(span_bytes_t old_bytes) noexcept#
inline void node_free_(std::size_t idx) noexcept#
inline node_t node_at_(std::size_t idx) const noexcept#
inline neighbors_ref_t neighbors_base_(node_t node) const noexcept#
inline neighbors_ref_t neighbors_non_base_(node_t node, level_t level) const noexcept#
inline neighbors_ref_t neighbors_(node_t node, level_t level) const noexcept#
inline node_lock_t node_lock_(std::size_t slot) const noexcept#
inline node_conditional_lock_t node_try_conditional_lock_(std::size_t slot, bool condition, bool &failed_to_acquire) const noexcept#
template<typename metric_at, bool require_non_empty_ak = false> inline candidates_view_t form_links_to_closest_ (metric_at &&metric, std::size_t new_slot, level_t level, context_t &context) usearch_noexcept_m
template<typename value_at, typename metric_at> inline void form_reverse_links_ (metric_at &&metric, compressed_slot_t new_slot, candidates_view_t new_neighbors, value_at &&value, level_t level, context_t &context) usearch_noexcept_m
inline level_t choose_random_level_(std::default_random_engine &level_generator) const noexcept#
template<typename value_at, typename metric_at, typename prefetch_at = dummy_prefetch_t>
inline compressed_slot_t search_for_one_(value_at &&query, metric_at &&metric, prefetch_at &&prefetch, compressed_slot_t closest_slot, level_t begin_level, level_t end_level, context_t &context) const noexcept#
template<typename value_at, typename metric_at, typename prefetch_at = dummy_prefetch_t>
inline bool search_to_insert_(value_at &&query, metric_at &&metric, prefetch_at &&prefetch, compressed_slot_t start_slot, level_t level, std::size_t top_limit, context_t &context) noexcept#

Traverses a layer of a graph, to find the best place to insert a new node. Locks the nodes in the process, assuming other threads are updating neighbors lists.

Returns:

true if procedure succeeded, false if run out of memory.

template<typename value_at, typename metric_at, typename prefetch_at = dummy_prefetch_t>
inline bool search_to_update_(value_at &&query, metric_at &&metric, prefetch_at &&prefetch, compressed_slot_t start_slot, compressed_slot_t updated_slot, level_t level, std::size_t top_limit, context_t &context) noexcept#

Traverses a layer of a graph, to find the best neighbors list for updated node. Locks the nodes in the process, assuming other threads are updating neighbors lists.

Returns:

true if procedure succeeded, false if run out of memory.

template<typename value_at, typename metric_at, typename predicate_at, typename prefetch_at> inline bool search_to_find_in_base_ (value_at &&query, metric_at &&metric, predicate_at &&predicate, prefetch_at &&prefetch, compressed_slot_t start_slot, std::size_t expansion, context_t &context) const usearch_noexcept_m

Traverses the base layer of a graph, to find a close match. Doesn’t lock any nodes, assuming read-only simultaneous access.

Returns:

true if procedure succeeded, false if run out of memory.

template<typename value_at, typename metric_at, typename predicate_at>
inline void search_exact_(value_at &&query, metric_at &&metric, predicate_at &&predicate, std::size_t count, context_t &context) const noexcept#

Iterates through all members, without actually touching the index.

template<typename metric_at>
inline candidates_view_t refine_(metric_at &&metric, std::size_t needed, top_candidates_t &top, context_t &context, std::size_t &refines_counter) const noexcept#

This algorithm from the original paper implements a heuristic, that massively reduces the number of connections a point has, to keep only the neighbors, that are from each other.

Private Members

mutable std::atomic<std::size_t> nodes_capacity_ = {}#

Number of “slots” available for node_t objects. Equals to .

mutable std::atomic<std::size_t> nodes_count_ = {}#

Number of “slots” already storing non-null nodes.

index_config_t config_ = {}#
index_limits_t limits_ = {}#
mutable dynamic_allocator_t dynamic_allocator_ = {}#
tape_allocator_t tape_allocator_ = {}#
precomputed_constants_t pre_ = {}#
memory_mapped_file_t viewed_file_ = {}#
std::mutex global_mutex_ = {}#

Controls access to max_level_ and entry_slot_. If any thread is updating those values, no other threads can add() or search().

level_t max_level_ = {}#

The level of the top-most graph in the index. Grows as the logarithm of size, starts from zero.

std::size_t entry_slot_ = {}#

The slot in which the only node of the top-level graph is stored.

buffer_gt<node_t, nodes_allocator_t> nodes_ = {}#

C-style array of node_t smart-pointers. Use compressed_slot_t for indexing.

mutable nodes_mutexes_t nodes_mutexes_ = {}#

Mutex, that limits concurrent access to nodes_.

mutable buffer_gt<context_t, contexts_allocator_t> contexts_ = {}#

Array of thread-specific buffers for temporary data.

Private Static Functions

static inline constexpr std::size_t node_head_bytes_()#

How many bytes of memory are needed to form the “head” of the node.

static inline precomputed_constants_t precompute_(index_config_t const &config) noexcept#
struct add_result_t#
#include <index.hpp>

Public Functions

inline explicit operator bool() const noexcept#
inline add_result_t failed(error_t message) noexcept#

Public Members

error_t error = {}#
std::size_t new_size = {}#
std::size_t visited_members = {}#
std::size_t computed_distances = {}#
std::size_t computed_distances_in_refines = {}#
std::size_t computed_distances_in_reverse_refines = {}#
compressed_slot_t slot = {}#
struct candidate_t#

A space-efficient internal data-structure used in graph traversal queues.

Public Functions

inline bool operator<(candidate_t other) const noexcept#

Public Members

distance_t distance#
compressed_slot_t slot#
class candidates_iterator_t#

Public Types

using element_t = compressed_slot_t#
using iterator_category = std::forward_iterator_tag#
using value_type = element_t#
using difference_type = std::ptrdiff_t#
using pointer = misaligned_ptr_gt<element_t>#
using reference = misaligned_ref_gt<element_t>#

Public Functions

inline value_type operator*() const noexcept#
inline candidates_iterator_t(index_gt const &index, neighbors_ref_t neighbors, visits_hash_set_t &visits, std::size_t progress) noexcept#
inline candidates_iterator_t operator++(int) noexcept#
inline candidates_iterator_t &operator++() noexcept#
inline bool operator==(candidates_iterator_t const &other) noexcept#
inline bool operator!=(candidates_iterator_t const &other) noexcept#
inline vector_key_t key() const noexcept#
inline compressed_slot_t slot() const noexcept#

Private Functions

inline candidates_iterator_t &skip_missing() noexcept#

Private Members

index_gt const &index_#
neighbors_ref_t neighbors_#
visits_hash_set_t &visits_#
std::size_t current_#

Friends

friend struct candidates_range_t
inline friend std::size_t get_slot(candidates_iterator_t const &it) noexcept#
inline friend vector_key_t get_key(candidates_iterator_t const &it) noexcept#
struct candidates_range_t#

Public Functions

inline candidates_iterator_t begin() const noexcept#
inline candidates_iterator_t end() const noexcept#

Public Members

index_gt const &index#
neighbors_ref_t neighbors#
visits_hash_set_t &visits#
struct cluster_result_t#
#include <index.hpp>

Public Functions

inline explicit operator bool() const noexcept#
inline cluster_result_t failed(error_t message) noexcept#

Public Members

error_t error = {}#
std::size_t visited_members = {}#
std::size_t computed_distances = {}#
match_t cluster = {}#
struct context_t#

A package of all kinds of temporary data-structures, that the threads would reuse to process requests. Similar to having all of those as separate thread_local global variables.

Public Functions

template<typename value_at, typename metric_at, typename entry_at>
inline distance_t measure(value_at const &first, entry_at const &second, metric_at &&metric) noexcept#

Heterogeneous distance calculation.

template<typename metric_at, typename entry_at>
inline distance_t measure(entry_at const &first, entry_at const &second, metric_at &&metric) noexcept#

Homogeneous distance calculation.

template<typename value_at, typename metric_at, typename entries_at, typename candidate_allowed_at, typename transform_at, typename callback_at>
inline void measure_batch(value_at const &first, entries_at const &second_entries, metric_at &&metric, candidate_allowed_at &&candidate_allowed, transform_at &&transform, callback_at &&callback) noexcept#

Heterogeneous batch distance calculation.

Public Members

top_candidates_t top_candidates = {}#
next_candidates_t next_candidates = {}#
visits_hash_set_t visits = {}#
std::default_random_engine level_generator = {}#
std::size_t iteration_cycles = {}#
std::size_t computed_distances = {}#
std::size_t computed_distances_in_refines = {}#
std::size_t computed_distances_in_reverse_refines = {}#
struct match_t#
#include <index.hpp>

Describes a matched search result, augmenting member_cref_t contents with distance to the query object.

Public Functions

inline match_t() noexcept#
inline match_t(member_cref_t member, distance_t distance) noexcept#
inline match_t(match_t &&other) noexcept#
inline match_t(match_t const &other) noexcept#
inline match_t &operator=(match_t const &other) noexcept#
inline match_t &operator=(match_t &&other) noexcept#

Public Members

member_cref_t member#
distance_t distance#
template<typename ref_at, typename index_at>
class member_iterator_gt#
#include <index.hpp>

Public Types

using iterator_category = std::random_access_iterator_tag#
using value_type = ref_t#
using difference_type = std::ptrdiff_t#
using pointer = void#
using reference = ref_t#

Public Functions

inline reference operator*() const noexcept#
inline vector_key_t key() const noexcept#
inline member_iterator_gt operator++(int) noexcept#
inline member_iterator_gt operator--(int) noexcept#
inline member_iterator_gt operator+(difference_type d) noexcept#
inline member_iterator_gt operator-(difference_type d) noexcept#
inline member_iterator_gt &operator++() noexcept#
inline member_iterator_gt &operator--() noexcept#
inline member_iterator_gt &operator+=(difference_type d) noexcept#
inline member_iterator_gt &operator-=(difference_type d) noexcept#
inline bool operator==(member_iterator_gt const &other) const noexcept#
inline bool operator!=(member_iterator_gt const &other) const noexcept#

Private Types

using ref_t = ref_at#
using index_t = index_at#

Private Functions

inline member_iterator_gt() noexcept#
inline member_iterator_gt(index_t *index, compressed_slot_t slot) noexcept#
template<int>
inline ref_t call_key(std::true_type) const noexcept#
template<int>
inline ref_t call_key(std::false_type) const noexcept#

Private Members

index_t *index_ = {}#
compressed_slot_t slot_ = {}#

Friends

friend class index_gt
inline friend compressed_slot_t get_slot(member_iterator_gt const &it) noexcept#
inline friend vector_key_t get_key(member_iterator_gt const &it) noexcept#
class neighbors_ref_t#

A slice of the node’s tape, containing a the list of neighbors for a node in a single graph level. It’s pre-allocated to fit as many neighbors “slots”, as may be needed at the target level, and starts with a single integer neighbors_count_t counter.

Public Types

using iterator = misaligned_ptr_gt<compressed_slot_t>#
using const_iterator = misaligned_ptr_gt<compressed_slot_t const>#
using value_type = compressed_slot_t#

Public Functions

inline neighbors_ref_t(byte_t *tape) noexcept#
inline misaligned_ptr_gt<compressed_slot_t> begin() noexcept#
inline misaligned_ptr_gt<compressed_slot_t> end() noexcept#
inline misaligned_ptr_gt<compressed_slot_t const> begin() const noexcept#
inline misaligned_ptr_gt<compressed_slot_t const> end() const noexcept#
inline misaligned_ptr_gt<compressed_slot_t const> cbegin() noexcept#
inline misaligned_ptr_gt<compressed_slot_t const> cend() noexcept#
inline compressed_slot_t operator[](std::size_t i) const noexcept#
inline std::size_t size() const noexcept#
inline void clear() noexcept#
inline void push_back(compressed_slot_t slot) noexcept#

Private Members

byte_t *tape_#

Private Static Functions

static inline constexpr std::size_t shift(std::size_t i = 0) noexcept#
struct node_conditional_lock_t#

Public Functions

inline ~node_conditional_lock_t() noexcept#

Public Members

nodes_mutexes_t &mutexes#
std::size_t slot#
struct node_lock_t#

Public Functions

inline ~node_lock_t() noexcept#

Public Members

nodes_mutexes_t &mutexes#