1#ifndef KNNCOLLE_BRUTEFORCE_HPP
2#define KNNCOLLE_BRUTEFORCE_HPP
26template<
typename Index_,
typename Data_,
typename Distance_,
typename DistanceMetric_>
40template<
typename Index_,
typename Data_,
typename Distance_,
class DistanceMetric_>
54 std::vector<std::pair<Distance_, Index_> > my_all_neighbors;
57 void normalize(std::vector<Distance_>* output_distances)
const {
58 if (output_distances) {
59 for (
auto& d : *output_distances) {
60 d = my_parent.my_metric->normalize(d);
66 void search(Index_ i, Index_ k, std::vector<Index_>* output_indices, std::vector<Distance_>* output_distances) {
67 my_nearest.
reset(k + 1);
68 auto ptr = my_parent.my_data.data() +
static_cast<std::size_t
>(i) * my_parent.my_dim;
69 my_parent.search(ptr, my_nearest);
70 my_nearest.
report(output_indices, output_distances, i);
71 normalize(output_distances);
74 void search(
const Data_* query, Index_ k, std::vector<Index_>* output_indices, std::vector<Distance_>* output_distances) {
77 output_indices->clear();
79 if (output_distances) {
80 output_distances->clear();
84 my_parent.search(query, my_nearest);
85 my_nearest.
report(output_indices, output_distances);
86 normalize(output_distances);
94 Index_
search_all(Index_ i, Distance_ d, std::vector<Index_>* output_indices, std::vector<Distance_>* output_distances) {
95 auto ptr = my_parent.my_data.data() +
static_cast<std::size_t
>(i) * my_parent.my_dim;
97 if (!output_indices && !output_distances) {
103 my_all_neighbors.clear();
106 normalize(output_distances);
111 Index_
search_all(
const Data_* query, Distance_ d, std::vector<Index_>* output_indices, std::vector<Distance_>* output_distances) {
112 if (!output_indices && !output_distances) {
118 my_all_neighbors.clear();
121 normalize(output_distances);
122 return my_all_neighbors.size();
138template<
typename Index_,
typename Data_,
typename Distance_,
class DistanceMetric_>
143 std::vector<Data_> my_data;
144 std::shared_ptr<const DistanceMetric_> my_metric;
150 BruteforcePrebuilt(std::size_t num_dim, Index_ num_obs, std::vector<Data_> data, std::shared_ptr<const DistanceMetric_> metric) :
151 my_dim(num_dim), my_obs(num_obs), my_data(std::move(data)), my_metric(std::move(metric)) {}
167 auto copy = my_data.data();
168 Distance_ threshold_raw = std::numeric_limits<Distance_>::infinity();
169 for (Index_ x = 0; x < my_obs; ++x, copy += my_dim) {
170 auto dist_raw = my_metric->raw(my_dim, query, copy);
171 if (dist_raw <= threshold_raw) {
172 nearest.
add(x, dist_raw);
174 threshold_raw = nearest.
limit();
180 template<
bool count_only_,
typename Output_>
181 void search_all(
const Data_* query, Distance_ threshold, Output_& all_neighbors)
const {
182 Distance_ threshold_raw = my_metric->denormalize(threshold);
183 auto copy = my_data.data();
184 for (Index_ x = 0; x < my_obs; ++x, copy += my_dim) {
185 Distance_ raw = my_metric->raw(my_dim, query, copy);
186 if (threshold_raw >= raw) {
187 if constexpr(count_only_) {
190 all_neighbors.emplace_back(raw, x);
196 friend class BruteforceSearcher<Index_, Data_, Distance_, DistanceMetric_>;
202 std::unique_ptr<Searcher<Index_, Data_, Distance_> >
initialize()
const {
203 return std::make_unique<BruteforceSearcher<Index_, Data_, Distance_, DistanceMetric_> >(*this);
227 class Matrix_ = Matrix<Index_, Data_>,
228 class DistanceMetric_ = DistanceMetric<Data_, Distance_>
235 BruteforceBuilder(std::shared_ptr<const DistanceMetric_> metric) : my_metric(std::move(metric)) {}
238 std::shared_ptr<const DistanceMetric_> my_metric;
245 std::size_t ndim = data.num_dimensions();
246 Index_ nobs = data.num_observations();
247 auto work = data.new_extractor();
249 std::vector<Data_> store(ndim *
static_cast<std::size_t
>(nobs));
250 for (Index_ o = 0; o < nobs; ++o) {
251 std::copy_n(work->next(), ndim, store.begin() +
static_cast<std::size_t
>(o) * ndim);
Interface to build nearest-neighbor indices.
Interface for the input matrix.
Helper class to track nearest neighbors.
Interface for prebuilt nearest-neighbor indices.
Interface for searching nearest-neighbor indices.
Perform a brute-force nearest neighbor search.
Definition Bruteforce.hpp:230
BruteforceBuilder(std::shared_ptr< const DistanceMetric_ > metric)
Definition Bruteforce.hpp:235
Prebuilt< Index_, Data_, Distance_ > * build_raw(const Matrix_ &data) const
Definition Bruteforce.hpp:244
Index for a brute-force nearest neighbor search.
Definition Bruteforce.hpp:139
Index_ num_observations() const
Definition Bruteforce.hpp:161
std::unique_ptr< Searcher< Index_, Data_, Distance_ > > initialize() const
Definition Bruteforce.hpp:202
std::size_t num_dimensions() const
Definition Bruteforce.hpp:157
Brute-force nearest neighbor searcher.
Definition Bruteforce.hpp:41
void search(Index_ i, Index_ k, std::vector< Index_ > *output_indices, std::vector< Distance_ > *output_distances)
Definition Bruteforce.hpp:66
Index_ search_all(Index_ i, Distance_ d, std::vector< Index_ > *output_indices, std::vector< Distance_ > *output_distances)
Definition Bruteforce.hpp:94
bool can_search_all() const
Definition Bruteforce.hpp:90
Index_ search_all(const Data_ *query, Distance_ d, std::vector< Index_ > *output_indices, std::vector< Distance_ > *output_distances)
Definition Bruteforce.hpp:111
void search(const Data_ *query, Index_ k, std::vector< Index_ > *output_indices, std::vector< Distance_ > *output_distances)
Definition Bruteforce.hpp:74
Interface to build nearest-neighbor search indices.
Definition Builder.hpp:28
Helper class to track nearest neighbors.
Definition NeighborQueue.hpp:30
void report(std::vector< Index_ > *output_indices, std::vector< Distance_ > *output_distances, Index_ self)
Definition NeighborQueue.hpp:109
void add(Index_ i, Distance_ d)
Definition NeighborQueue.hpp:83
Distance_ limit() const
Definition NeighborQueue.hpp:71
bool is_full() const
Definition NeighborQueue.hpp:63
void reset(Index_ k)
Definition NeighborQueue.hpp:46
Interface for prebuilt nearest-neighbor search indices.
Definition Prebuilt.hpp:28
Interface for searching nearest-neighbor search indices.
Definition Searcher.hpp:28
Classes for distance calculations.
Collection of KNN algorithms.
Definition Bruteforce.hpp:24
Index_ count_all_neighbors_without_self(Index_ count)
Definition report_all_neighbors.hpp:23
void report_all_neighbors(std::vector< std::pair< Distance_, Index_ > > &all_neighbors, std::vector< Index_ > *output_indices, std::vector< Distance_ > *output_distances, Index_ self)
Definition report_all_neighbors.hpp:106
Format the output for Searcher::search_all().