Plugins/Hashing/AnnoyTest.cpp

0001 // This file is part of the ACTS project.
0002 //
0003 // Copyright (C) 2016 CERN for the benefit of the ACTS project
0004 //
0005 // This Source Code Form is subject to the terms of the Mozilla Public
0006 // License, v. 2.0. If a copy of the MPL was not distributed with this
0007 // file, You can obtain one at https://mozilla.org/MPL/2.0/.
0008
0009 #include <boost/test/unit_test.hpp>
0010
0011 #include <array>
0012 #include <cstdint>
0013 #include <vector>
0014
0015 #include <annoy/annoylib.h>
0016 #include <annoy/kissrandom.h>
0017
0018 namespace {
0019 // Test vector of 2D points generated from the make_blobs function of
0020 // scikit-learn to correspond to 4 clusters with a standard deviation of 0.3
0021 std::vector<std::array<double, 2>> testVector{
0022     {-2.83739915, 2.62792556},  {-2.02847331, -1.90722196},
0023     {4.42609249, -2.42439165},  {-2.54167208, -1.31586441},
0024     {-2.74072011, 1.88175176},  {-2.44805173, -1.72270269},
0025     {4.32373114, -3.04946856},  {-3.02908065, 3.05502207},
0026     {4.21551681, -2.72367792},  {6.94454243, -8.26702198},
0027     {4.57729285, -2.98832874},  {-2.05999536, -1.60664607},
0028     {7.29942963, -7.49254664},  {-1.76560555, -1.94316957},
0029     {-3.08697607, 2.38012823},  {-2.68133439, -1.96863594},
0030     {-3.04707961, 2.42381653},  {-1.6693666 - 1.98996212},
0031     {4.87565038, -2.42067792},  {6.57829525 - 8.14269767},
0032     {-1.89777458, -1.71029565}, {-2.82010574, 2.27963425},
0033     {-1.8938416, -1.76676642},  {-2.8088788, 2.14373147},
0034     {-2.7111892, 2.7343114},    {5.00997563, -3.03311654},
0035     {-3.00272791, 1.59086316},  {-2.69800242, 2.19671366},
0036     {5.35757875, -2.98359632},  {6.41134781, -7.79582109},
0037     {5.06123223, -2.84952632},  {6.33969189, -7.83811637},
0038     {5.11101701, -2.80965778},  {7.01442234, -7.47047664},
0039     {6.82239627, -7.97467806},  {6.82647513, -7.64299033},
0040     {-2.02651791, -1.81791892}, {-2.53859699, -2.20157508},
0041     {5.07240334, -2.48183097},  {-1.58869273, -2.30974576},
0042     {5.24011121, -2.78045434},  {4.89256735, -2.98154234},
0043     {-2.61589554, -1.38994103}, {-2.37898031, 2.02633106},
0044     {6.71148996, -7.87697906},  {-2.24310299, -2.01958434},
0045     {4.80875851, -3.00716459},  {-2.20240163, -1.45942015},
0046     {5.0317719, -3.33571147},   {4.68497184, -2.2794554},
0047     {6.57950453, -7.84613618},  {-2.39557904, -0.97990746},
0048     {4.89489222, -3.31597619},  {5.22670358, -2.79577779},
0049     {4.87625814, -2.70562793},  {5.37121464, -2.78439938},
0050     {6.48510206, -7.89652351},  {-2.78153003, 1.79940689},
0051     {6.80163025, -7.7267214},   {-2.42494396, -1.95543603},
0052     {7.01502605, -7.93922357},  {-2.00219795, -1.95198446},
0053     {-2.82690524, 1.83749478},  {-2.81153684, 2.30020325},
0054     {-1.46316156, -1.70854783}, {-2.36754202, -1.62836379},
0055     {-3.12179904, 1.86079695},  {-2.80228975, 2.16674687},
0056     {7.25447808, -7.87780152},  {6.34182023, -7.72244414},
0057     {6.85296593, -7.6565112},   {6.40782187, -7.95817435},
0058     {4.60981662, -2.6214774},   {6.82470403, -7.8453859},
0059     {-2.94909893, 2.4408267},   {6.48588252, -8.42529572},
0060     {6.55194867, -7.54354929},  {-2.64178285, 2.28031333},
0061     {-1.95664147, -2.44817923}, {-2.00957937, -2.01412199},
0062     {-2.24603999, 2.48964234},  {4.73274418, -2.89077558},
0063     {-2.47534453, 1.85935482},  {-2.35722712, -1.99652695},
0064     {5.15661108, -2.88549784},  {6.68114631, -7.73743642},
0065     {4.93268708, -2.97510717},  {6.54260932, -8.82618456},
0066     {-3.57448792, 2.06852256},  {6.63296723, -8.32752766},
0067     {-3.58610661, 2.2761471},   {-2.73077783, 1.8138345},
0068     {-2.14150912, 1.94984708},  {-2.27235876, -1.67574786},
0069     {6.92208545, -8.46326386},  {4.58953972, -3.22764749},
0070     {-3.36912131, 2.58470911},  {5.28526348, -2.55723196},
0071     {6.55276593, -7.81387909},  {-1.79854507, -2.10170986}};
0072 }  // namespace
0073
0074 namespace Acts::Test {
0075
0076 BOOST_AUTO_TEST_CASE(AnnoySetSeedTest) {
0077   using AnnoyMetric = Annoy::Euclidean;
0078   using AnnoyModel =
0079       Annoy::AnnoyIndex<unsigned int, double, AnnoyMetric, Annoy::Kiss32Random,
0080                         Annoy::AnnoyIndexSingleThreadedBuildPolicy>;
0081
0082   const unsigned int annoySeed = 123456789;
0083   const std::int32_t f = 2;
0084
0085   AnnoyModel annoyModel = AnnoyModel(f);
0086
0087   annoyModel.set_seed(annoySeed);
0088
0089   BOOST_CHECK_EQUAL(annoyModel.get_seed(), annoySeed);
0090 }
0091
0092 BOOST_AUTO_TEST_CASE(AnnoyAddAndBuildTest) {
0093   using AnnoyMetric = Annoy::Euclidean;
0094   using AnnoyModel =
0095       Annoy::AnnoyIndex<unsigned int, double, AnnoyMetric, Annoy::Kiss32Random,
0096                         Annoy::AnnoyIndexSingleThreadedBuildPolicy>;
0097
0098   const unsigned int annoySeed = 123456789;
0099   const std::int32_t f = 2;
0100
0101   AnnoyModel annoyModel = AnnoyModel(f);
0102
0103   annoyModel.set_seed(annoySeed);
0104
0105   unsigned int pointIndex = 0;
0106   // Add spacePoints parameters to Annoy
0107   for (const auto& arrayvec : testVector) {
0108     annoyModel.add_item(pointIndex, arrayvec.data());
0109     pointIndex++;
0110   }
0111
0112   unsigned int nTrees = 2 * f;
0113
0114   annoyModel.build(nTrees);
0115
0116   /// Get the bucketSize closest spacePoints
0117   unsigned int bucketSize = 5;
0118   std::vector<unsigned int> bucketIds;
0119   annoyModel.get_nns_by_item(0, bucketSize, -1, &bucketIds, nullptr);
0120
0121   BOOST_CHECK_EQUAL(bucketIds.size(), bucketSize);
0122 }
0123
0124 BOOST_AUTO_TEST_CASE(AnnoyNeighborTest) {
0125   using AnnoyMetric = Annoy::Euclidean;
0126   using AnnoyModel =
0127       Annoy::AnnoyIndex<unsigned int, double, AnnoyMetric, Annoy::Kiss32Random,
0128                         Annoy::AnnoyIndexSingleThreadedBuildPolicy>;
0129
0130   const unsigned int annoySeed = 123456789;
0131   const std::int32_t f = 2;
0132
0133   AnnoyModel annoyModel = AnnoyModel(f);
0134
0135   annoyModel.set_seed(annoySeed);
0136
0137   unsigned int pointIndex = 0;
0138   // Add spacePoints parameters to Annoy
0139   for (const auto& arrayvec : testVector) {
0140     annoyModel.add_item(pointIndex, arrayvec.data());
0141     pointIndex++;
0142   }
0143
0144   unsigned int nTrees = 2 * f;
0145
0146   annoyModel.build(nTrees);
0147
0148   /// Validate neighbors for the first point
0149   unsigned int bucketSize = 5;
0150   std::vector<unsigned int> bucketIds;
0151   std::vector<double> distances;
0152   annoyModel.get_nns_by_item(0, bucketSize, -1, &bucketIds, &distances);
0153
0154   BOOST_CHECK_EQUAL(bucketIds.size(), bucketSize);
0155   BOOST_CHECK_EQUAL(distances.size(), bucketSize);
0156
0157   // Check that the first item is the closest to itself
0158   BOOST_CHECK_EQUAL(bucketIds[0], 0);
0159
0160   // Check the distances are sorted in ascending order
0161   for (std::size_t i = 1; i < distances.size(); ++i) {
0162     BOOST_CHECK(distances[i] >= distances[i - 1]);
0163   }
0164 }
0165
0166 BOOST_AUTO_TEST_CASE(AnnoyDistanceTest) {
0167   using AnnoyMetric = Annoy::Euclidean;
0168   using AnnoyModel =
0169       Annoy::AnnoyIndex<unsigned int, double, AnnoyMetric, Annoy::Kiss32Random,
0170                         Annoy::AnnoyIndexSingleThreadedBuildPolicy>;
0171
0172   const unsigned int annoySeed = 123456789;
0173   const std::int32_t f = 2;
0174
0175   AnnoyModel annoyModel = AnnoyModel(f);
0176
0177   annoyModel.set_seed(annoySeed);
0178
0179   unsigned int pointIndex = 0;
0180   // Add spacePoints parameters to Annoy
0181   for (const auto& arrayvec : testVector) {
0182     annoyModel.add_item(pointIndex, arrayvec.data());
0183     pointIndex++;
0184   }
0185
0186   unsigned int nTrees = 2 * f;
0187
0188   annoyModel.build(nTrees);
0189
0190   /// Validate the distance computation
0191   double distance = annoyModel.get_distance(0, 1);
0192   double expected_distance =
0193       std::sqrt(std::pow(testVector[0][0] - testVector[1][0], 2) +
0194                 std::pow(testVector[0][1] - testVector[1][1], 2));
0195
0196   BOOST_CHECK_CLOSE(distance, expected_distance, 1e-5);
0197 }
0198
0199 }  // namespace Acts::Test