| 1 |
//---------------------------------------------------------------------- |
| 2 |
// File: ann_test.cpp |
| 3 |
// Programmer: Sunil Arya and David Mount |
| 4 |
// Description: test program for ANN (approximate nearest neighbors) |
| 5 |
// Last modified: 01/27/10 (Version 1.1.2) |
| 6 |
//---------------------------------------------------------------------- |
| 7 |
// Copyright (c) 1997-2010 University of Maryland and Sunil Arya and |
| 8 |
// David Mount. All Rights Reserved. |
| 9 |
// |
| 10 |
// This software and related documentation is part of the Approximate |
| 11 |
// Nearest Neighbor Library (ANN). This software is provided under |
| 12 |
// the provisions of the Lesser GNU Public License (LGPL). See the |
| 13 |
// file ../ReadMe.txt for further information. |
| 14 |
// |
| 15 |
// The University of Maryland (U.M.) and the authors make no |
| 16 |
// representations about the suitability or fitness of this software for |
| 17 |
// any purpose. It is provided "as is" without express or implied |
| 18 |
// warranty. |
| 19 |
//---------------------------------------------------------------------- |
| 20 |
// History: |
| 21 |
// Revision 0.1 03/04/98 |
| 22 |
// Initial release |
| 23 |
// Revision 0.2 06/26/98 |
| 24 |
// Added CLOCKS_PER_SEC definition if needed |
| 25 |
// Revision 1.0 04/01/05 |
| 26 |
// Added comments (from "#" to eol) |
| 27 |
// Added clus_orth_flats and clus_ellipsoids distributions |
| 28 |
// Fixed order of fair and midpt in split_table |
| 29 |
// Added dump/load operations |
| 30 |
// Cleaned up C++ for modern compilers |
| 31 |
// Revision 1.1 05/03/05 |
| 32 |
// Added fixed radius kNN search |
| 33 |
// Revision 1.1.1 08/04/06 |
| 34 |
// Added planted distribution |
| 35 |
// Revision 1.1.2 01/27/10 |
| 36 |
// Fixed minor compilation bugs for new versions of gcc |
| 37 |
// Allow round-off error in validation test |
| 38 |
//---------------------------------------------------------------------- |
| 39 |
|
| 40 |
#include <ctime> // clock |
| 41 |
#include <cmath> // math routines |
| 42 |
#include <cstring> // C string ops |
| 43 |
#include <fstream> // file I/O |
| 44 |
|
| 45 |
#include <ANN/ANN.h> // ANN declarations |
| 46 |
#include <ANN/ANNx.h> // more ANN declarations |
| 47 |
#include <ANN/ANNperf.h> // performance evaluation |
| 48 |
|
| 49 |
#include "rand.h" // random point generation |
| 50 |
|
| 51 |
#ifndef CLOCKS_PER_SEC // define clocks-per-second if needed |
| 52 |
#define CLOCKS_PER_SEC 1000000 |
| 53 |
#endif |
| 54 |
|
| 55 |
using namespace std; // make std:: available |
| 56 |
|
| 57 |
//---------------------------------------------------------------------- |
| 58 |
// ann_test |
| 59 |
// |
| 60 |
// This program is a driver for testing and evaluating the ANN library |
| 61 |
// for computing approximate nearest neighbors. It allows the user to |
| 62 |
// generate data and query sets of various sizes, dimensions, and |
| 63 |
// distributions, to build kd- and bbd-trees of various types, and then |
| 64 |
// run queries and outputting various performance statistics. |
| 65 |
// |
| 66 |
// Overview: |
| 67 |
// --------- |
| 68 |
// The test program is run as follows: |
| 69 |
// |
| 70 |
// ann_test < test_input > test_output |
| 71 |
// |
| 72 |
// where the test_input file contains a list of directives as described |
| 73 |
// below. Directives consist of a directive name, followed by list of |
| 74 |
// arguments (depending on the directive). Arguments and directives are |
| 75 |
// separated by white space (blank, tab, and newline). String arguments |
| 76 |
// are not quoted, and consist of a string of nonwhite chacters. A |
| 77 |
// character "#" denotes a comment. The following characters up to |
| 78 |
// the end of line are ignored. Comments may only be inserted between |
| 79 |
// directives (not within the argument list of a directive). |
| 80 |
// |
| 81 |
// Basic operations: |
| 82 |
// ----------------- |
| 83 |
// The test program can perform the following operations. How these |
| 84 |
// operations are performed depends on the options which are described |
| 85 |
// later. |
| 86 |
// |
| 87 |
// Data Generation: |
| 88 |
// ---------------- |
| 89 |
// read_data_pts <file> Create a set of data points whose |
| 90 |
// coordinates are input from file <file>. |
| 91 |
// gen_data_pts Create a set of data points whose |
| 92 |
// coordinates are generated from the |
| 93 |
// current point distribution. |
| 94 |
// |
| 95 |
// Building the tree: |
| 96 |
// ------------------ |
| 97 |
// build_ann Generate an approximate nearest neighbor |
| 98 |
// structure for the current data set, using |
| 99 |
// the selected splitting rules. Any existing |
| 100 |
// tree will be destroyed. |
| 101 |
// |
| 102 |
// Query Generation/Searching: |
| 103 |
// --------------------------- |
| 104 |
// read_query_pts <file> Create a set of query points whose |
| 105 |
// coordinates are input from file <file>. |
| 106 |
// gen_query_pts Create a set of query points whose |
| 107 |
// coordinates are generated from the |
| 108 |
// current point distribution. |
| 109 |
// run_queries <string> Apply nearest neighbor searching to the |
| 110 |
// query points using the approximate nearest |
| 111 |
// neighbor structure and the given search |
| 112 |
// strategy. Possible strategies are: |
| 113 |
// standard = standard kd-tree search |
| 114 |
// priority = priority search |
| 115 |
// |
| 116 |
// Miscellaneous: |
| 117 |
// -------------- |
| 118 |
// output_label Output a label to the output file. |
| 119 |
// dump <file> Dump the current structure to given file. |
| 120 |
// (The dump format is explained further in |
| 121 |
// the source file kd_tree.cc.) |
| 122 |
// load <file> Load a tree from a data file which was |
| 123 |
// created by the dump operation. Any |
| 124 |
// existing tree will be destroyed. |
| 125 |
// |
| 126 |
// Options: |
| 127 |
// -------- |
| 128 |
// How these operations are performed depends on a set of options. |
| 129 |
// If an option is not specified, a default value is used. An option |
| 130 |
// retains its value until it is set again. String inputs are not |
| 131 |
// enclosed in quotes, and must contain no embedded white space (sorry, |
| 132 |
// this is C++'s convention). |
| 133 |
// |
| 134 |
// Options affecting search tree structure: |
| 135 |
// ---------------------------------------- |
| 136 |
// split_rule <type> Type of splitting rule to use in building |
| 137 |
// the search tree. Choices are: |
| 138 |
// kd = optimized kd-tree |
| 139 |
// midpt = midpoint split |
| 140 |
// fair = fair split |
| 141 |
// sl_midpt = sliding midpt split |
| 142 |
// sl_fair = sliding fair split |
| 143 |
// suggest = authors' choice for best |
| 144 |
// The default is "suggest". See the file |
| 145 |
// kd_split.cc for more detailed information. |
| 146 |
// |
| 147 |
// shrink_rule <type> Type of shrinking rule to use in building |
| 148 |
// a bd-tree data structure. If "none" is |
| 149 |
// given, then no shrinking is performed and |
| 150 |
// the result is a kd-tree. Choices are: |
| 151 |
// none = perform no shrinking |
| 152 |
// simple = simple shrinking |
| 153 |
// centroid = centroid shrinking |
| 154 |
// suggest = authors' choice for best |
| 155 |
// The default is "none". See the file |
| 156 |
// bd_tree.cc for more information. |
| 157 |
// bucket_size <int> Bucket size, that is, the maximum number of |
| 158 |
// points stored in each leaf node. |
| 159 |
// |
| 160 |
// Options affecting data and query point generation: |
| 161 |
// -------------------------------------------------- |
| 162 |
// dim <int> Dimension of space. |
| 163 |
// seed <int> Seed for random number generation. |
| 164 |
// data_size <int> Number of data points. When reading data |
| 165 |
// points from a file, this indicates the |
| 166 |
// maximum number of points for storage |
| 167 |
// allocation. Default = 100. |
| 168 |
// query_size <int> Same as data_size for query points. |
| 169 |
// std_dev <float> Standard deviation (used in gauss, |
| 170 |
// planted, and clustered distributions). |
| 171 |
// This is the "small" distribution for |
| 172 |
// clus_ellipsoids. Default = 1. |
| 173 |
// std_dev_lo <float> Low and high standard deviations (used in |
| 174 |
// std_dev_hi <float> clus_ellipsoids). Default = 1. |
| 175 |
// corr_coef <float> Correlation coefficient (used in co-gauss |
| 176 |
// and co_lapace distributions). Default = 0.05. |
| 177 |
// colors <int> Number of color classes (clusters) (used |
| 178 |
// in the clustered distributions). Default = 5. |
| 179 |
// new_clust Once generated, cluster centers are not |
| 180 |
// normally regenerated. This is so that both |
| 181 |
// query points and data points can be generated |
| 182 |
// using the same set of clusters. This option |
| 183 |
// forces new cluster centers to be generated |
| 184 |
// with the next generation of either data or |
| 185 |
// query points. |
| 186 |
// max_clus_dim <int> Maximum dimension of clusters (used in |
| 187 |
// clus_orth_flats and clus_ellipsoids). |
| 188 |
// Default = 1. |
| 189 |
// distribution <string> Type of input distribution |
| 190 |
// uniform = uniform over cube [-1,1]^d. |
| 191 |
// gauss = Gaussian with mean 0 |
| 192 |
// laplace = Laplacian, mean 0 and var 1 |
| 193 |
// co_gauss = correlated Gaussian |
| 194 |
// co_laplace = correlated Laplacian |
| 195 |
// clus_gauss = clustered Gaussian |
| 196 |
// clus_orth_flats = clusters of orth flats |
| 197 |
// clus_ellipsoids = clusters of ellipsoids |
| 198 |
// planted = planted distribution |
| 199 |
// See the file rand.cpp for further information. |
| 200 |
// |
| 201 |
// Options affecting nearest neighbor search: |
| 202 |
// ------------------------------------------ |
| 203 |
// epsilon <float> Error bound for approx. near neigh. search. |
| 204 |
// near_neigh <int> Number of nearest neighbors to compute. |
| 205 |
// max_pts_visit <int> Maximum number of points to visit before |
| 206 |
// terminating. (Used in applications where |
| 207 |
// real-time performance is important.) |
| 208 |
// (Default = 0, which means no limit.) |
| 209 |
// radius_bound <float> Sets an upper bound on the nearest |
| 210 |
// neighbor search radius. If the bound is |
| 211 |
// positive, then fixed-radius nearest |
| 212 |
// neighbor searching is performed, and the |
| 213 |
// count of the number of points in the |
| 214 |
// range is returned. If the bound is |
| 215 |
// zero, then standard search is used. |
| 216 |
// This can only be used with standard, not |
| 217 |
// priority, search. (Default = 0, which |
| 218 |
// means standard search.) |
| 219 |
// |
| 220 |
// Options affection general program behavior: |
| 221 |
// ------------------------------------------- |
| 222 |
// stats <string> Level of statistics output |
| 223 |
// silent = no output, |
| 224 |
// exec_time += execution time only |
| 225 |
// prep_stats += preprocessing statistics |
| 226 |
// query_stats += query performance stats |
| 227 |
// query_res += results of queries |
| 228 |
// show_pts += show the data points |
| 229 |
// show_struct += print search structure |
| 230 |
// validate <string> Validate experiment and compute average |
| 231 |
// error. Since validation causes exact |
| 232 |
// nearest neighbors to be computed by the |
| 233 |
// brute force method, this can take a long |
| 234 |
// time. Valid arguments are: |
| 235 |
// on = turn validation on |
| 236 |
// off = turn validation off |
| 237 |
// true_near_neigh <int> Number of true nearest neighbors to compute. |
| 238 |
// When validating, we compute the difference |
| 239 |
// in rank between each reported nearest neighbor |
| 240 |
// and the true nearest neighbor of the same |
| 241 |
// rank. Thus it is necessary to compute a |
| 242 |
// few more true nearest neighbors. By default |
| 243 |
// we compute 10 more than near_neigh. With |
| 244 |
// this option the exact number can be set. |
| 245 |
// (Used only when validating.) |
| 246 |
// |
| 247 |
// Example: |
| 248 |
// -------- |
| 249 |
// output_label test_run_0 # output label for this run |
| 250 |
// validate off # do not perform validation |
| 251 |
// dim 16 # points in dimension 16 |
| 252 |
// stats query_stats # output performance statistics for queries |
| 253 |
// seed 121212 # random number seed |
| 254 |
// data_size 1000 |
| 255 |
// distribution uniform |
| 256 |
// gen_data_pts # 1000 uniform data points in dim 16 |
| 257 |
// query_size 100 |
| 258 |
// std_dev 0.05 |
| 259 |
// distribution clus_gauss |
| 260 |
// gen_query_pts # 100 points in 10 clusters with std_dev 0.05 |
| 261 |
// bucket_size 2 |
| 262 |
// split_rule kd |
| 263 |
// shrink_rule none |
| 264 |
// build_ann # kd-tree, bucket size 2 |
| 265 |
// epsilon 0.1 |
| 266 |
// near_neigh 5 |
| 267 |
// max_pts_visit 100 # stop search if more than 100 points seen |
| 268 |
// run_queries standard # run queries; 5 nearest neighbors, 10% error |
| 269 |
// data_size 500 |
| 270 |
// read_data_pts data.in # read up to 500 points from file data.in |
| 271 |
// split_rule sl_midpt |
| 272 |
// shrink_rule simple |
| 273 |
// build_ann # bd-tree; simple shrink, sliding midpoint split |
| 274 |
// epsilon 0 |
| 275 |
// run_queries priority # run same queries; 0 allowable error |
| 276 |
// |
| 277 |
//------------------------------------------------------------------------ |
| 278 |
|
| 279 |
//------------------------------------------------------------------------ |
| 280 |
// Constants |
| 281 |
//------------------------------------------------------------------------ |
| 282 |
|
| 283 |
const int STRING_LEN = 500; // max string length |
| 284 |
const double ERR = 0.00001; // epsilon (for float compares) |
| 285 |
const double RND_OFF = 5E-16; // double round-off error |
| 286 |
|
| 287 |
//------------------------------------------------------------------------ |
| 288 |
// Enumerated values and conversions |
| 289 |
//------------------------------------------------------------------------ |
| 290 |
|
| 291 |
typedef enum {DATA, QUERY} PtType; // point types |
| 292 |
|
| 293 |
//------------------------------------------------------------------------ |
| 294 |
// Statistics output levels |
| 295 |
//------------------------------------------------------------------------ |
| 296 |
|
| 297 |
typedef enum { // stat levels |
| 298 |
SILENT, // no output |
| 299 |
EXEC_TIME, // just execution time |
| 300 |
PREP_STATS, // preprocessing info |
| 301 |
QUERY_STATS, // query performance |
| 302 |
QUERY_RES, // query results |
| 303 |
SHOW_PTS, // show data points |
| 304 |
SHOW_STRUCT, // show tree structure |
| 305 |
N_STAT_LEVELS} // number of levels |
| 306 |
StatLev; |
| 307 |
|
| 308 |
const char stat_table[N_STAT_LEVELS][STRING_LEN] = { |
| 309 |
"silent", // SILENT |
| 310 |
"exec_time", // EXEC_TIME |
| 311 |
"prep_stats", // PREP_STATS |
| 312 |
"query_stats", // QUERY_STATS |
| 313 |
"query_res", // QUERY_RES |
| 314 |
"show_pts", // SHOW_PTS |
| 315 |
"show_struct"}; // SHOW_STRUCT |
| 316 |
|
| 317 |
//------------------------------------------------------------------------ |
| 318 |
// Distributions |
| 319 |
//------------------------------------------------------------------------ |
| 320 |
|
| 321 |
typedef enum { // distributions |
| 322 |
UNIFORM, // uniform over cube [-1,1]^d. |
| 323 |
GAUSS, // Gaussian with mean 0 |
| 324 |
LAPLACE, // Laplacian, mean 0 and var 1 |
| 325 |
CO_GAUSS, // correlated Gaussian |
| 326 |
CO_LAPLACE, // correlated Laplacian |
| 327 |
CLUS_GAUSS, // clustered Gaussian |
| 328 |
CLUS_ORTH_FLATS, // clustered on orthog flats |
| 329 |
CLUS_ELLIPSOIDS, // clustered on ellipsoids |
| 330 |
PLANTED, // planted distribution |
| 331 |
N_DISTRIBS} |
| 332 |
Distrib; |
| 333 |
|
| 334 |
const char distr_table[N_DISTRIBS][STRING_LEN] = { |
| 335 |
"uniform", // UNIFORM |
| 336 |
"gauss", // GAUSS |
| 337 |
"laplace", // LAPLACE |
| 338 |
"co_gauss", // CO_GAUSS |
| 339 |
"co_laplace", // CO_LAPLACE |
| 340 |
"clus_gauss", // CLUS_GAUSS |
| 341 |
"clus_orth_flats", // CLUS_ORTH_FLATS |
| 342 |
"clus_ellipsoids", // CLUS_ELLIPSOIS |
| 343 |
"planted"}; // PLANTED |
| 344 |
|
| 345 |
//------------------------------------------------------------------------ |
| 346 |
// Splitting rules for kd-trees (see ANN.h for types) |
| 347 |
//------------------------------------------------------------------------ |
| 348 |
|
| 349 |
const int N_SPLIT_RULES = 6; |
| 350 |
const char split_table[N_SPLIT_RULES][STRING_LEN] = { |
| 351 |
"standard", // standard optimized kd-tree |
| 352 |
"midpt", // midpoint split |
| 353 |
"fair", // fair split |
| 354 |
"sl_midpt", // sliding midpt split |
| 355 |
"sl_fair", // sliding fair split |
| 356 |
"suggest"}; // authors' choice for best |
| 357 |
|
| 358 |
//------------------------------------------------------------------------ |
| 359 |
// Shrinking rules for bd-trees (see ANN.h for types) |
| 360 |
//------------------------------------------------------------------------ |
| 361 |
|
| 362 |
const int N_SHRINK_RULES = 4; |
| 363 |
const char shrink_table[N_SHRINK_RULES][STRING_LEN] = { |
| 364 |
"none", // perform no shrinking (kd-tree) |
| 365 |
"simple", // simple shrinking |
| 366 |
"centroid", // centroid shrinking |
| 367 |
"suggest"}; // authors' choice for best |
| 368 |
|
| 369 |
//---------------------------------------------------------------------- |
| 370 |
// Short utility functions |
| 371 |
// Error - general error routine |
| 372 |
// printPoint - print a point to standard output |
| 373 |
// lookUp - look up a name in table and return index |
| 374 |
//---------------------------------------------------------------------- |
| 375 |
|
| 376 |
void Error( // error routine |
| 377 |
const char* msg, // error message |
| 378 |
ANNerr level) // abort afterwards |
| 379 |
{ |
| 380 |
if (level == ANNabort) { |
| 381 |
cerr << "ann_test: ERROR------->" << msg << "<-------------ERROR\n"; |
| 382 |
exit(1); |
| 383 |
} |
| 384 |
else { |
| 385 |
cerr << "ann_test: WARNING----->" << msg << "<-------------WARNING\n"; |
| 386 |
} |
| 387 |
} |
| 388 |
|
| 389 |
void printPoint( // print point |
| 390 |
ANNpoint p, // the point |
| 391 |
int dim) // the dimension |
| 392 |
{ |
| 393 |
cout << "["; |
| 394 |
for (int i = 0; i < dim; i++) { |
| 395 |
cout << p[i]; |
| 396 |
if (i < dim-1) cout << ","; |
| 397 |
} |
| 398 |
cout << "]"; |
| 399 |
} |
| 400 |
|
| 401 |
int lookUp( // look up name in table |
| 402 |
const char* arg, // name to look up |
| 403 |
const char (*table)[STRING_LEN], // name table |
| 404 |
int size) // table size |
| 405 |
{ |
| 406 |
int i; |
| 407 |
for (i = 0; i < size; i++) { |
| 408 |
if (!strcmp(arg, table[i])) return i; |
| 409 |
} |
| 410 |
return i; |
| 411 |
} |
| 412 |
|
| 413 |
//------------------------------------------------------------------------ |
| 414 |
// Function declarations |
| 415 |
//------------------------------------------------------------------------ |
| 416 |
|
| 417 |
void generatePts( // generate data/query points |
| 418 |
ANNpointArray &pa, // point array (returned) |
| 419 |
int n, // number of points |
| 420 |
PtType type, // point type |
| 421 |
ANNbool new_clust, // new cluster centers desired? |
| 422 |
ANNpointArray src = NULL, // source array (for PLANTED) |
| 423 |
int n_src = 0); // source size (for PLANTED) |
| 424 |
|
| 425 |
void readPts( // read data/query points from file |
| 426 |
ANNpointArray &pa, // point array (returned) |
| 427 |
int &n, // number of points |
| 428 |
char *file_nm, // file name |
| 429 |
PtType type); // point type (DATA, QUERY) |
| 430 |
|
| 431 |
void doValidation(); // perform validation |
| 432 |
void getTrueNN(); // compute true nearest neighbors |
| 433 |
|
| 434 |
void treeStats( // print statistics on kd- or bd-tree |
| 435 |
ostream &out, // output stream |
| 436 |
ANNbool verbose); // print stats |
| 437 |
|
| 438 |
//------------------------------------------------------------------------ |
| 439 |
// Default execution parameters |
| 440 |
//------------------------------------------------------------------------ |
| 441 |
const int extra_nn = 10; // how many extra true nn's? |
| 442 |
|
| 443 |
const int def_dim = 2; // def dimension |
| 444 |
const int def_data_size = 100; // def data size |
| 445 |
const int def_query_size = 100; // def number of queries |
| 446 |
const int def_n_color = 5; // def number of colors |
| 447 |
const ANNbool def_new_clust = ANNfalse; // def new clusters flag |
| 448 |
const int def_max_dim = 1; // def max flat dimension |
| 449 |
const Distrib def_distr = UNIFORM; // def distribution |
| 450 |
const double def_std_dev = 1.00; // def standard deviation |
| 451 |
const double def_corr_coef = 0.05; // def correlation coef |
| 452 |
const int def_bucket_size = 1; // def bucket size |
| 453 |
const double def_epsilon = 0.0; // def error bound |
| 454 |
const int def_near_neigh = 1; // def number of near neighbors |
| 455 |
const int def_max_visit = 0; // def number of points visited |
| 456 |
const int def_rad_bound = 0; // def radius bound |
| 457 |
// def number of true nn's |
| 458 |
const int def_true_nn = def_near_neigh + extra_nn; |
| 459 |
const int def_seed = 0; // def seed for random numbers |
| 460 |
const ANNbool def_validate = ANNfalse; // def validation flag |
| 461 |
// def statistics output level |
| 462 |
const StatLev def_stats = QUERY_STATS; |
| 463 |
const ANNsplitRule // def splitting rule |
| 464 |
def_split = ANN_KD_SUGGEST; |
| 465 |
const ANNshrinkRule // def shrinking rule |
| 466 |
def_shrink = ANN_BD_NONE; |
| 467 |
|
| 468 |
//------------------------------------------------------------------------ |
| 469 |
// Global variables - Execution options |
| 470 |
//------------------------------------------------------------------------ |
| 471 |
|
| 472 |
int dim; // dimension |
| 473 |
int data_size; // data size |
| 474 |
int query_size; // number of queries |
| 475 |
int n_color; // number of colors |
| 476 |
ANNbool new_clust; // generate new clusters? |
| 477 |
int max_dim; // maximum flat dimension |
| 478 |
Distrib distr; // distribution |
| 479 |
double corr_coef; // correlation coef |
| 480 |
double std_dev; // standard deviation |
| 481 |
double std_dev_lo; // low standard deviation |
| 482 |
double std_dev_hi; // high standard deviation |
| 483 |
int bucket_size; // bucket size |
| 484 |
double epsilon; // error bound |
| 485 |
int near_neigh; // number of near neighbors |
| 486 |
int max_pts_visit; // max number of points to visit |
| 487 |
double radius_bound; // maximum radius search bound |
| 488 |
int true_nn; // number of true nn's |
| 489 |
ANNbool validate; // validation flag |
| 490 |
StatLev stats; // statistics output level |
| 491 |
ANNsplitRule split; // splitting rule |
| 492 |
ANNshrinkRule shrink; // shrinking rule |
| 493 |
|
| 494 |
//------------------------------------------------------------------------ |
| 495 |
// More globals - pointers to dynamically allocated arrays and structures |
| 496 |
// |
| 497 |
// It is assumed that all these values are set to NULL when nothing |
| 498 |
// is allocated. |
| 499 |
// |
| 500 |
// data_pts, query_pts The data and query points |
| 501 |
// the_tree Points to the kd- or bd-tree for |
| 502 |
// nearest neighbor searching. |
| 503 |
// apx_nn_idx, apx_dists Record approximate near neighbor |
| 504 |
// indices and distances |
| 505 |
// apx_pts_in_range Counts of the number of points in |
| 506 |
// the in approx range, for fixed- |
| 507 |
// radius NN searching. |
| 508 |
// true_nn_idx, true_dists Record true near neighbor |
| 509 |
// indices and distances |
| 510 |
// min_pts_in_range, max_... Min and max counts of the number |
| 511 |
// of points in the in approximate |
| 512 |
// range. |
| 513 |
// valid_dirty To avoid repeated validation, |
| 514 |
// we only validate query results |
| 515 |
// once. This validation becomes |
| 516 |
// invalid, if a new tree, new data |
| 517 |
// points or new query points have |
| 518 |
// been generated. |
| 519 |
// tree_data_size The number of points in the |
| 520 |
// current tree. (This will be the |
| 521 |
// same a data_size unless points have |
| 522 |
// been added since the tree was |
| 523 |
// built.) |
| 524 |
// |
| 525 |
// The approximate and true nearest neighbor results are stored |
| 526 |
// in: apx_nn_idx, apx_dists, and true_nn_idx, true_dists. |
| 527 |
// They are really flattened 2-dimensional arrays. Each of these |
| 528 |
// arrays consists of query_size blocks, each of which contains |
| 529 |
// near_neigh (or true_nn) entries, one for each of the nearest |
| 530 |
// neighbors for a given query point. |
| 531 |
//------------------------------------------------------------------------ |
| 532 |
|
| 533 |
ANNpointArray data_pts; // data points |
| 534 |
ANNpointArray query_pts; // query points |
| 535 |
ANNbd_tree* the_tree; // kd- or bd-tree search structure |
| 536 |
ANNidxArray apx_nn_idx; // storage for near neighbor indices |
| 537 |
ANNdistArray apx_dists; // storage for near neighbor distances |
| 538 |
int* apx_pts_in_range; // storage for no. of points in range |
| 539 |
ANNidxArray true_nn_idx; // true near neighbor indices |
| 540 |
ANNdistArray true_dists; // true near neighbor distances |
| 541 |
int* min_pts_in_range; // min points in approx range |
| 542 |
int* max_pts_in_range; // max points in approx range |
| 543 |
|
| 544 |
ANNbool valid_dirty; // validation is no longer valid |
| 545 |
|
| 546 |
//------------------------------------------------------------------------ |
| 547 |
// Initialize global parameters |
| 548 |
//------------------------------------------------------------------------ |
| 549 |
|
| 550 |
void initGlobals() |
| 551 |
{ |
| 552 |
dim = def_dim; // init execution parameters |
| 553 |
data_size = def_data_size; |
| 554 |
query_size = def_query_size; |
| 555 |
distr = def_distr; |
| 556 |
corr_coef = def_corr_coef; |
| 557 |
std_dev = def_std_dev; |
| 558 |
std_dev_lo = def_std_dev; |
| 559 |
std_dev_hi = def_std_dev; |
| 560 |
new_clust = def_new_clust; |
| 561 |
max_dim = def_max_dim; |
| 562 |
n_color = def_n_color; |
| 563 |
bucket_size = def_bucket_size; |
| 564 |
epsilon = def_epsilon; |
| 565 |
near_neigh = def_near_neigh; |
| 566 |
max_pts_visit = def_max_visit; |
| 567 |
radius_bound = def_rad_bound; |
| 568 |
true_nn = def_true_nn; |
| 569 |
validate = def_validate; |
| 570 |
stats = def_stats; |
| 571 |
split = def_split; |
| 572 |
shrink = def_shrink; |
| 573 |
annIdum = -def_seed; // init. global seed for ran0() |
| 574 |
|
| 575 |
data_pts = NULL; // initialize storage pointers |
| 576 |
query_pts = NULL; |
| 577 |
the_tree = NULL; |
| 578 |
apx_nn_idx = NULL; |
| 579 |
apx_dists = NULL; |
| 580 |
apx_pts_in_range = NULL; |
| 581 |
true_nn_idx = NULL; |
| 582 |
true_dists = NULL; |
| 583 |
min_pts_in_range = NULL; |
| 584 |
max_pts_in_range = NULL; |
| 585 |
|
| 586 |
valid_dirty = ANNtrue; // (validation must be done) |
| 587 |
} |
| 588 |
|
| 589 |
//------------------------------------------------------------------------ |
| 590 |
// getDirective - skip comments and read next directive |
| 591 |
// Returns ANNtrue if directive read, and ANNfalse if eof seen. |
| 592 |
//------------------------------------------------------------------------ |
| 593 |
|
| 594 |
ANNbool skipComment( // skip any comments |
| 595 |
istream &in) // input stream |
| 596 |
{ |
| 597 |
char ch = 0; |
| 598 |
// skip whitespace |
| 599 |
do { in.get(ch); } while (isspace(ch) && !in.eof()); |
| 600 |
while (ch == '#' && !in.eof()) { // comment? |
| 601 |
// skip to end of line |
| 602 |
do { in.get(ch); } while(ch != '\n' && !in.eof()); |
| 603 |
// skip whitespace |
| 604 |
do { in.get(ch); } while(isspace(ch) && !in.eof()); |
| 605 |
} |
| 606 |
if (in.eof()) return ANNfalse; // end of file |
| 607 |
in.putback(ch); // put character back |
| 608 |
return ANNtrue; |
| 609 |
} |
| 610 |
|
| 611 |
ANNbool getDirective( |
| 612 |
istream &in, // input stream |
| 613 |
char *directive) // directive storage |
| 614 |
{ |
| 615 |
if (!skipComment(in)) // skip comments |
| 616 |
return ANNfalse; // found eof along the way? |
| 617 |
in >> directive; // read directive |
| 618 |
return ANNtrue; |
| 619 |
} |
| 620 |
|
| 621 |
|
| 622 |
//------------------------------------------------------------------------ |
| 623 |
// main program - driver |
| 624 |
// The main program reads input options, invokes the necessary |
| 625 |
// routines to process them. |
| 626 |
//------------------------------------------------------------------------ |
| 627 |
|
| 628 |
int main(int argc, char** argv) |
| 629 |
{ |
| 630 |
long clock0; // clock time |
| 631 |
char directive[STRING_LEN]; // input directive |
| 632 |
char arg[STRING_LEN]; // all-purpose argument |
| 633 |
|
| 634 |
cout << "------------------------------------------------------------\n" |
| 635 |
<< "ann_test: Version " << ANNversion << " " << ANNversionCmt << "\n" |
| 636 |
<< " Copyright: " << ANNcopyright << ".\n" |
| 637 |
<< " Latest Revision: " << ANNlatestRev << ".\n" |
| 638 |
<< "------------------------------------------------------------\n\n"; |
| 639 |
|
| 640 |
initGlobals(); // initialize global values |
| 641 |
|
| 642 |
//-------------------------------------------------------------------- |
| 643 |
// Main input loop |
| 644 |
//-------------------------------------------------------------------- |
| 645 |
// read input directive |
| 646 |
while (getDirective(cin, directive)) { |
| 647 |
//---------------------------------------------------------------- |
| 648 |
// Read options |
| 649 |
//---------------------------------------------------------------- |
| 650 |
if (!strcmp(directive,"dim")) { |
| 651 |
cin >> dim; |
| 652 |
} |
| 653 |
else if (!strcmp(directive,"colors")) { |
| 654 |
cin >> n_color; |
| 655 |
} |
| 656 |
else if (!strcmp(directive,"new_clust")) { |
| 657 |
new_clust = ANNtrue; |
| 658 |
} |
| 659 |
else if (!strcmp(directive,"max_clus_dim")) { |
| 660 |
cin >> max_dim; |
| 661 |
} |
| 662 |
else if (!strcmp(directive,"std_dev")) { |
| 663 |
cin >> std_dev; |
| 664 |
} |
| 665 |
else if (!strcmp(directive,"std_dev_lo")) { |
| 666 |
cin >> std_dev_lo; |
| 667 |
} |
| 668 |
else if (!strcmp(directive,"std_dev_hi")) { |
| 669 |
cin >> std_dev_hi; |
| 670 |
} |
| 671 |
else if (!strcmp(directive,"corr_coef")) { |
| 672 |
cin >> corr_coef; |
| 673 |
} |
| 674 |
else if (!strcmp(directive, "data_size")) { |
| 675 |
cin >> data_size; |
| 676 |
} |
| 677 |
else if (!strcmp(directive,"query_size")) { |
| 678 |
cin >> query_size; |
| 679 |
} |
| 680 |
else if (!strcmp(directive,"bucket_size")) { |
| 681 |
cin >> bucket_size; |
| 682 |
} |
| 683 |
else if (!strcmp(directive,"epsilon")) { |
| 684 |
cin >> epsilon; |
| 685 |
} |
| 686 |
else if (!strcmp(directive,"max_pts_visit")) { |
| 687 |
cin >> max_pts_visit; |
| 688 |
valid_dirty = ANNtrue; // validation must be redone |
| 689 |
} |
| 690 |
else if (!strcmp(directive,"radius_bound")) { |
| 691 |
cin >> radius_bound; |
| 692 |
valid_dirty = ANNtrue; // validation must be redone |
| 693 |
} |
| 694 |
else if (!strcmp(directive,"near_neigh")) { |
| 695 |
cin >> near_neigh; |
| 696 |
true_nn = near_neigh + extra_nn; // also reset true near neighs |
| 697 |
valid_dirty = ANNtrue; // validation must be redone |
| 698 |
} |
| 699 |
else if (!strcmp(directive,"true_near_neigh")) { |
| 700 |
cin >> true_nn; |
| 701 |
valid_dirty = ANNtrue; // validation must be redone |
| 702 |
} |
| 703 |
//---------------------------------------------------------------- |
| 704 |
// seed option |
| 705 |
// The seed is reset by setting the global annIdum to the |
| 706 |
// negation of the seed value. See rand.cpp. |
| 707 |
//---------------------------------------------------------------- |
| 708 |
else if (!strcmp(directive,"seed")) { |
| 709 |
cin >> annIdum; |
| 710 |
annIdum = -annIdum; |
| 711 |
} |
| 712 |
//---------------------------------------------------------------- |
| 713 |
// validate option |
| 714 |
//---------------------------------------------------------------- |
| 715 |
else if (!strcmp(directive,"validate")) { |
| 716 |
cin >> arg; // input argument |
| 717 |
if (!strcmp(arg, "on")) { |
| 718 |
validate = ANNtrue; |
| 719 |
cout << "validate = on " |
| 720 |
<< "(Warning: this may slow execution time.)\n"; |
| 721 |
} |
| 722 |
else if (!strcmp(arg, "off")) { |
| 723 |
validate = ANNfalse; |
| 724 |
} |
| 725 |
else { |
| 726 |
cerr << "Argument: " << arg << "\n"; |
| 727 |
Error("validate argument must be \"on\" or \"off\"", ANNabort); |
| 728 |
} |
| 729 |
} |
| 730 |
//---------------------------------------------------------------- |
| 731 |
// distribution option |
| 732 |
//---------------------------------------------------------------- |
| 733 |
else if (!strcmp(directive,"distribution")) { |
| 734 |
cin >> arg; // input name and translate |
| 735 |
distr = (Distrib) lookUp(arg, distr_table, N_DISTRIBS); |
| 736 |
if (distr >= N_DISTRIBS) { // not something we recognize |
| 737 |
cerr << "Distribution: " << arg << "\n"; |
| 738 |
Error("Unknown distribution", ANNabort); |
| 739 |
} |
| 740 |
} |
| 741 |
//---------------------------------------------------------------- |
| 742 |
// stats option |
| 743 |
//---------------------------------------------------------------- |
| 744 |
else if (!strcmp(directive,"stats")) { |
| 745 |
cin >> arg; // input name and translate |
| 746 |
stats = (StatLev) lookUp(arg, stat_table, N_STAT_LEVELS); |
| 747 |
if (stats >= N_STAT_LEVELS) { // not something we recognize |
| 748 |
cerr << "Stats level: " << arg << "\n"; |
| 749 |
Error("Unknown statistics level", ANNabort); |
| 750 |
} |
| 751 |
if (stats > SILENT) |
| 752 |
cout << "stats = " << arg << "\n"; |
| 753 |
} |
| 754 |
//---------------------------------------------------------------- |
| 755 |
// split_rule option |
| 756 |
//---------------------------------------------------------------- |
| 757 |
else if (!strcmp(directive,"split_rule")) { |
| 758 |
cin >> arg; // input split_rule name |
| 759 |
split = (ANNsplitRule) lookUp(arg, split_table, N_SPLIT_RULES); |
| 760 |
if (split >= N_SPLIT_RULES) { // not something we recognize |
| 761 |
cerr << "Splitting rule: " << arg << "\n"; |
| 762 |
Error("Unknown splitting rule", ANNabort); |
| 763 |
} |
| 764 |
} |
| 765 |
//---------------------------------------------------------------- |
| 766 |
// shrink_rule option |
| 767 |
//---------------------------------------------------------------- |
| 768 |
else if (!strcmp(directive,"shrink_rule")) { |
| 769 |
cin >> arg; // input split_rule name |
| 770 |
shrink = (ANNshrinkRule) lookUp(arg, shrink_table, N_SHRINK_RULES); |
| 771 |
if (shrink >= N_SHRINK_RULES) { // not something we recognize |
| 772 |
cerr << "Shrinking rule: " << arg << "\n"; |
| 773 |
Error("Unknown shrinking rule", ANNabort); |
| 774 |
} |
| 775 |
} |
| 776 |
//---------------------------------------------------------------- |
| 777 |
// label operation |
| 778 |
//---------------------------------------------------------------- |
| 779 |
else if (!strcmp(directive,"output_label")) { |
| 780 |
cin >> arg; |
| 781 |
if (stats > SILENT) |
| 782 |
cout << "<" << arg << ">\n"; |
| 783 |
} |
| 784 |
//---------------------------------------------------------------- |
| 785 |
// gen_data_pts operation |
| 786 |
//---------------------------------------------------------------- |
| 787 |
else if (!strcmp(directive,"gen_data_pts")) { |
| 788 |
if (distr == PLANTED) { // planted distribution |
| 789 |
Error("Cannot use planted distribution for data points", ANNabort); |
| 790 |
} |
| 791 |
generatePts( // generate data points |
| 792 |
data_pts, // data points |
| 793 |
data_size, // data size |
| 794 |
DATA, // data points |
| 795 |
new_clust); // new clusters flag |
| 796 |
valid_dirty = ANNtrue; // validation must be redone |
| 797 |
new_clust = ANNfalse; // reset flag |
| 798 |
} |
| 799 |
//---------------------------------------------------------------- |
| 800 |
// gen_query_pts operation |
| 801 |
// If the distribution is PLANTED, then the query points |
| 802 |
// are planted near the data points (which must already be |
| 803 |
// generated). |
| 804 |
//---------------------------------------------------------------- |
| 805 |
else if (!strcmp(directive,"gen_query_pts")) { |
| 806 |
if (distr == PLANTED) { // planted distribution |
| 807 |
if (data_pts == NULL) { |
| 808 |
Error("Must generate data points before query points for planted distribution", ANNabort); |
| 809 |
} |
| 810 |
generatePts( // generate query points |
| 811 |
query_pts, // point array |
| 812 |
query_size, // number of query points |
| 813 |
QUERY, // query points |
| 814 |
new_clust, // new clusters flag |
| 815 |
data_pts, // plant around data pts |
| 816 |
data_size); |
| 817 |
} |
| 818 |
else { // all other distributions |
| 819 |
generatePts( // generate query points |
| 820 |
query_pts, // point array |
| 821 |
query_size, // number of query points |
| 822 |
QUERY, // query points |
| 823 |
new_clust); // new clusters flag |
| 824 |
} |
| 825 |
valid_dirty = ANNtrue; // validation must be redone |
| 826 |
new_clust = ANNfalse; // reset flag |
| 827 |
} |
| 828 |
//---------------------------------------------------------------- |
| 829 |
// read_data_pts operation |
| 830 |
//---------------------------------------------------------------- |
| 831 |
else if (!strcmp(directive,"read_data_pts")) { |
| 832 |
cin >> arg; // input file name |
| 833 |
readPts( |
| 834 |
data_pts, // point array |
| 835 |
data_size, // number of points |
| 836 |
arg, // file name |
| 837 |
DATA); // data points |
| 838 |
valid_dirty = ANNtrue; // validation must be redone |
| 839 |
} |
| 840 |
//---------------------------------------------------------------- |
| 841 |
// read_query_pts operation |
| 842 |
//---------------------------------------------------------------- |
| 843 |
else if (!strcmp(directive,"read_query_pts")) { |
| 844 |
cin >> arg; // input file name |
| 845 |
readPts( |
| 846 |
query_pts, // point array |
| 847 |
query_size, // number of points |
| 848 |
arg, // file name |
| 849 |
QUERY); // query points |
| 850 |
valid_dirty = ANNtrue; // validation must be redone |
| 851 |
} |
| 852 |
//---------------------------------------------------------------- |
| 853 |
// build_ann operation |
| 854 |
// We always invoke the constructor for bd-trees. Note |
| 855 |
// that when the shrinking rule is NONE (which is true by |
| 856 |
// default), then this constructs a kd-tree. |
| 857 |
//---------------------------------------------------------------- |
| 858 |
else if (!strcmp(directive,"build_ann")) { |
| 859 |
//------------------------------------------------------------ |
| 860 |
// Build the tree |
| 861 |
//------------------------------------------------------------ |
| 862 |
if (the_tree != NULL) { // tree exists already |
| 863 |
delete the_tree; // get rid of it |
| 864 |
} |
| 865 |
clock0 = clock(); // start time |
| 866 |
|
| 867 |
the_tree = new ANNbd_tree( // build it |
| 868 |
data_pts, // the data points |
| 869 |
data_size, // number of points |
| 870 |
dim, // dimension of space |
| 871 |
bucket_size, // maximum bucket size |
| 872 |
split, // splitting rule |
| 873 |
shrink); // shrinking rule |
| 874 |
|
| 875 |
//------------------------------------------------------------ |
| 876 |
// Print summary |
| 877 |
//------------------------------------------------------------ |
| 878 |
long prep_time = clock() - clock0; // end of prep time |
| 879 |
|
| 880 |
if (stats > SILENT) { |
| 881 |
cout << "[Build ann-structure:\n"; |
| 882 |
cout << " split_rule = " << split_table[split] << "\n"; |
| 883 |
cout << " shrink_rule = " << shrink_table[shrink] << "\n"; |
| 884 |
cout << " data_size = " << data_size << "\n"; |
| 885 |
cout << " dim = " << dim << "\n"; |
| 886 |
cout << " bucket_size = " << bucket_size << "\n"; |
| 887 |
|
| 888 |
if (stats >= EXEC_TIME) { // output processing time |
| 889 |
cout << " process_time = " |
| 890 |
<< double(prep_time)/CLOCKS_PER_SEC << " sec\n"; |
| 891 |
} |
| 892 |
|
| 893 |
if (stats >= PREP_STATS) // output or check tree stats |
| 894 |
treeStats(cout, ANNtrue); // print tree stats |
| 895 |
else |
| 896 |
treeStats(cout, ANNfalse); // check stats |
| 897 |
|
| 898 |
if (stats >= SHOW_STRUCT) { // print the whole tree |
| 899 |
cout << " (Structure Contents:\n"; |
| 900 |
the_tree->Print(ANNfalse, cout); |
| 901 |
cout << " )\n"; |
| 902 |
} |
| 903 |
cout << "]\n"; |
| 904 |
} |
| 905 |
} |
| 906 |
//---------------------------------------------------------------- |
| 907 |
// dump operation |
| 908 |
//---------------------------------------------------------------- |
| 909 |
else if (!strcmp(directive,"dump")) { |
| 910 |
cin >> arg; // input file name |
| 911 |
if (the_tree == NULL) { // no tree |
| 912 |
Error("Cannot dump. No tree has been built yet", ANNwarn); |
| 913 |
} |
| 914 |
else { // there is a tree |
| 915 |
// try to open file |
| 916 |
ofstream out_dump_file(arg); |
| 917 |
if (!out_dump_file) { |
| 918 |
cerr << "File name: " << arg << "\n"; |
| 919 |
Error("Cannot open dump file", ANNabort); |
| 920 |
} |
| 921 |
// dump the tree and points |
| 922 |
the_tree->Dump(ANNtrue, out_dump_file); |
| 923 |
if (stats > SILENT) { |
| 924 |
cout << "(Tree has been dumped to file " << arg << ")\n"; |
| 925 |
} |
| 926 |
} |
| 927 |
} |
| 928 |
//---------------------------------------------------------------- |
| 929 |
// load operation |
| 930 |
// Since this not only loads a tree, but loads a new set |
| 931 |
// of data points. |
| 932 |
//---------------------------------------------------------------- |
| 933 |
else if (!strcmp(directive,"load")) { |
| 934 |
cin >> arg; // input file name |
| 935 |
if (the_tree != NULL) { // tree exists already |
| 936 |
delete the_tree; // get rid of it |
| 937 |
} |
| 938 |
if (data_pts != NULL) { // data points exist already |
| 939 |
delete data_pts; // get rid of them |
| 940 |
} |
| 941 |
|
| 942 |
ifstream in_dump_file(arg); // try to open file |
| 943 |
if (!in_dump_file) { |
| 944 |
cerr << "File name: " << arg << "\n"; |
| 945 |
Error("Cannot open file for loading", ANNabort); |
| 946 |
} |
| 947 |
// build tree by loading |
| 948 |
the_tree = new ANNbd_tree(in_dump_file); |
| 949 |
|
| 950 |
dim = the_tree->theDim(); // new dimension |
| 951 |
data_size = the_tree->nPoints(); // number of points |
| 952 |
data_pts = the_tree->thePoints(); // new points |
| 953 |
|
| 954 |
valid_dirty = ANNtrue; // validation must be redone |
| 955 |
|
| 956 |
if (stats > SILENT) { |
| 957 |
cout << "(Tree has been loaded from file " << arg << ")\n"; |
| 958 |
} |
| 959 |
if (stats >= SHOW_STRUCT) { // print the tree |
| 960 |
cout << " (Structure Contents:\n"; |
| 961 |
the_tree->Print(ANNfalse, cout); |
| 962 |
cout << " )\n"; |
| 963 |
} |
| 964 |
} |
| 965 |
//---------------------------------------------------------------- |
| 966 |
// run_queries operation |
| 967 |
// This section does all the query processing. It consists |
| 968 |
// of the following subsections: |
| 969 |
// |
| 970 |
// ** input the argument (standard or priority) and output |
| 971 |
// the header describing the essential information. |
| 972 |
// ** allocate space for the results to be stored. |
| 973 |
// ** run the queries by invoking the appropriate search |
| 974 |
// procedure on the query points. Print nearest neighbor |
| 975 |
// if requested. |
| 976 |
// ** print final summaries |
| 977 |
// |
| 978 |
// The approach for processing multiple nearest neighbors is |
| 979 |
// pretty crude. We allocate an array whose size is the |
| 980 |
// product of the total number of queries times the number of |
| 981 |
// nearest neighbors (k), and then use each k consecutive |
| 982 |
// entries to store the results of each query. |
| 983 |
//---------------------------------------------------------------- |
| 984 |
else if (!strcmp(directive,"run_queries")) { |
| 985 |
|
| 986 |
//------------------------------------------------------------ |
| 987 |
// Input arguments and print summary |
| 988 |
//------------------------------------------------------------ |
| 989 |
enum {STANDARD, PRIORITY} method; |
| 990 |
|
| 991 |
cin >> arg; // input argument |
| 992 |
if (!strcmp(arg, "standard")) { |
| 993 |
method = STANDARD; |
| 994 |
} |
| 995 |
else if (!strcmp(arg, "priority")) { |
| 996 |
method = PRIORITY; |
| 997 |
} |
| 998 |
else { |
| 999 |
cerr << "Search type: " << arg << "\n"; |
| 1000 |
Error("Search type must be \"standard\" or \"priority\"", |
| 1001 |
ANNabort); |
| 1002 |
} |
| 1003 |
if (data_pts == NULL || query_pts == NULL) { |
| 1004 |
Error("Either data set and query set not constructed", ANNabort); |
| 1005 |
} |
| 1006 |
if (the_tree == NULL) { |
| 1007 |
Error("No search tree built.", ANNabort); |
| 1008 |
} |
| 1009 |
|
| 1010 |
//------------------------------------------------------------ |
| 1011 |
// Set up everything |
| 1012 |
//------------------------------------------------------------ |
| 1013 |
|
| 1014 |
#ifdef ANN_PERF // performance only |
| 1015 |
annResetStats(data_size); // reset statistics |
| 1016 |
#endif |
| 1017 |
|
| 1018 |
clock0 = clock(); // start time |
| 1019 |
// deallocate existing storage |
| 1020 |
if (apx_nn_idx != NULL) delete [] apx_nn_idx; |
| 1021 |
if (apx_dists != NULL) delete [] apx_dists; |
| 1022 |
if (apx_pts_in_range != NULL) delete [] apx_pts_in_range; |
| 1023 |
// allocate apx answer storage |
| 1024 |
apx_nn_idx = new ANNidx[near_neigh*query_size]; |
| 1025 |
apx_dists = new ANNdist[near_neigh*query_size]; |
| 1026 |
apx_pts_in_range = new int[query_size]; |
| 1027 |
|
| 1028 |
annMaxPtsVisit(max_pts_visit); // set max points to visit |
| 1029 |
|
| 1030 |
//------------------------------------------------------------ |
| 1031 |
// Run the queries |
| 1032 |
//------------------------------------------------------------ |
| 1033 |
// pointers for current query |
| 1034 |
ANNidxArray curr_nn_idx = apx_nn_idx; |
| 1035 |
ANNdistArray curr_dists = apx_dists; |
| 1036 |
|
| 1037 |
for (int i = 0; i < query_size; i++) { |
| 1038 |
#ifdef ANN_PERF |
| 1039 |
annResetCounts(); // reset counters |
| 1040 |
#endif |
| 1041 |
apx_pts_in_range[i] = 0; |
| 1042 |
|
| 1043 |
if (radius_bound == 0) { // no radius bound |
| 1044 |
if (method == STANDARD) { |
| 1045 |
the_tree->annkSearch( |
| 1046 |
query_pts[i], // query point |
| 1047 |
near_neigh, // number of near neighbors |
| 1048 |
curr_nn_idx, // nearest neighbors (returned) |
| 1049 |
curr_dists, // distance (returned) |
| 1050 |
epsilon); // error bound |
| 1051 |
} |
| 1052 |
else if (method == PRIORITY) { |
| 1053 |
the_tree->annkPriSearch( |
| 1054 |
query_pts[i], // query point |
| 1055 |
near_neigh, // number of near neighbors |
| 1056 |
curr_nn_idx, // nearest neighbors (returned) |
| 1057 |
curr_dists, // distance (returned) |
| 1058 |
epsilon); // error bound |
| 1059 |
} |
| 1060 |
else { |
| 1061 |
Error("Internal error - invalid method", ANNabort); |
| 1062 |
} |
| 1063 |
} |
| 1064 |
else { // use radius bound |
| 1065 |
if (method != STANDARD) { |
| 1066 |
Error("A nonzero radius bound assumes standard search", |
| 1067 |
ANNwarn); |
| 1068 |
} |
| 1069 |
apx_pts_in_range[i] = the_tree->annkFRSearch( |
| 1070 |
query_pts[i], // query point |
| 1071 |
ANN_POW(radius_bound), // squared radius search bound |
| 1072 |
near_neigh, // number of near neighbors |
| 1073 |
curr_nn_idx, // nearest neighbors (returned) |
| 1074 |
curr_dists, // distance (returned) |
| 1075 |
epsilon); // error bound |
| 1076 |
} |
| 1077 |
curr_nn_idx += near_neigh; // increment current pointers |
| 1078 |
curr_dists += near_neigh; |
| 1079 |
|
| 1080 |
#ifdef ANN_PERF |
| 1081 |
annUpdateStats(); // update stats |
| 1082 |
#endif |
| 1083 |
} |
| 1084 |
|
| 1085 |
long query_time = clock() - clock0; // end of query time |
| 1086 |
|
| 1087 |
if (validate) { // validation requested |
| 1088 |
if (valid_dirty) getTrueNN(); // get true near neighbors |
| 1089 |
doValidation(); // validate |
| 1090 |
} |
| 1091 |
|
| 1092 |
//------------------------------------------------------------ |
| 1093 |
// Print summaries |
| 1094 |
//------------------------------------------------------------ |
| 1095 |
|
| 1096 |
if (stats > SILENT) { |
| 1097 |
cout << "[Run Queries:\n"; |
| 1098 |
cout << " query_size = " << query_size << "\n"; |
| 1099 |
cout << " dim = " << dim << "\n"; |
| 1100 |
cout << " search_method = " << arg << "\n"; |
| 1101 |
cout << " epsilon = " << epsilon << "\n"; |
| 1102 |
cout << " near_neigh = " << near_neigh << "\n"; |
| 1103 |
if (max_pts_visit != 0) |
| 1104 |
cout << " max_pts_visit = " << max_pts_visit << "\n"; |
| 1105 |
if (radius_bound != 0) |
| 1106 |
cout << " radius_bound = " << radius_bound << "\n"; |
| 1107 |
if (validate) |
| 1108 |
cout << " true_nn = " << true_nn << "\n"; |
| 1109 |
|
| 1110 |
if (stats >= EXEC_TIME) { // print exec time summary |
| 1111 |
cout << " query_time = " << |
| 1112 |
double(query_time)/(query_size*CLOCKS_PER_SEC) |
| 1113 |
<< " sec/query"; |
| 1114 |
#ifdef ANN_PERF |
| 1115 |
cout << " (biased by perf measurements)"; |
| 1116 |
#endif |
| 1117 |
cout << "\n"; |
| 1118 |
} |
| 1119 |
|
| 1120 |
if (stats >= QUERY_STATS) { // output performance stats |
| 1121 |
#ifdef ANN_PERF |
| 1122 |
cout.flush(); |
| 1123 |
annPrintStats(validate); |
| 1124 |
#else |
| 1125 |
cout << " (Performance statistics unavailable.)\n"; |
| 1126 |
#endif |
| 1127 |
} |
| 1128 |
|
| 1129 |
if (stats >= QUERY_RES) { // output results |
| 1130 |
cout << " (Query Results:\n"; |
| 1131 |
cout << " Pt\tANN\tDist\n"; |
| 1132 |
curr_nn_idx = apx_nn_idx; // subarray pointers |
| 1133 |
curr_dists = apx_dists; |
| 1134 |
// output nearest neighbors |
| 1135 |
for (int i = 0; i < query_size; i++) { |
| 1136 |
cout << " " << setw(4) << i; |
| 1137 |
for (int j = 0; j < near_neigh; j++) { |
| 1138 |
// exit if no more neighbors |
| 1139 |
if (curr_nn_idx[j] == ANN_NULL_IDX) { |
| 1140 |
cout << "\t[no other pts in radius bound]\n"; |
| 1141 |
break; |
| 1142 |
} |
| 1143 |
else { // output point info |
| 1144 |
cout << "\t" << curr_nn_idx[j] |
| 1145 |
<< "\t" << ANN_ROOT(curr_dists[j]) |
| 1146 |
<< "\n"; |
| 1147 |
} |
| 1148 |
} |
| 1149 |
// output range count |
| 1150 |
if (radius_bound != 0) { |
| 1151 |
cout << " pts_in_radius_bound = " |
| 1152 |
<< apx_pts_in_range[i] << "\n"; |
| 1153 |
} |
| 1154 |
// increment subarray pointers |
| 1155 |
curr_nn_idx += near_neigh; |
| 1156 |
curr_dists += near_neigh; |
| 1157 |
} |
| 1158 |
cout << " )\n"; |
| 1159 |
} |
| 1160 |
cout << "]\n"; |
| 1161 |
} |
| 1162 |
} |
| 1163 |
//---------------------------------------------------------------- |
| 1164 |
// Unknown directive |
| 1165 |
//---------------------------------------------------------------- |
| 1166 |
else { |
| 1167 |
cerr << "Directive: " << directive << "\n"; |
| 1168 |
Error("Unknown directive", ANNabort); |
| 1169 |
} |
| 1170 |
} |
| 1171 |
//-------------------------------------------------------------------- |
| 1172 |
// End of input loop (deallocate stuff that was allocated) |
| 1173 |
//-------------------------------------------------------------------- |
| 1174 |
if (the_tree != NULL) delete the_tree; |
| 1175 |
if (data_pts != NULL) annDeallocPts(data_pts); |
| 1176 |
if (query_pts != NULL) annDeallocPts(query_pts); |
| 1177 |
if (apx_nn_idx != NULL) delete [] apx_nn_idx; |
| 1178 |
if (apx_dists != NULL) delete [] apx_dists; |
| 1179 |
if (apx_pts_in_range != NULL) delete [] apx_pts_in_range; |
| 1180 |
|
| 1181 |
annClose(); // close ANN |
| 1182 |
|
| 1183 |
return EXIT_SUCCESS; |
| 1184 |
} |
| 1185 |
|
| 1186 |
//------------------------------------------------------------------------ |
| 1187 |
// generatePts - call appropriate routine to generate points of a |
| 1188 |
// given distribution. |
| 1189 |
//------------------------------------------------------------------------ |
| 1190 |
|
| 1191 |
void generatePts( |
| 1192 |
ANNpointArray &pa, // point array (returned) |
| 1193 |
int n, // number of points to generate |
| 1194 |
PtType type, // point type |
| 1195 |
ANNbool new_clust, // new cluster centers desired? |
| 1196 |
ANNpointArray src, // source array (if distr=PLANTED) |
| 1197 |
int n_src) // source size (if distr=PLANTED) |
| 1198 |
{ |
| 1199 |
if (pa != NULL) annDeallocPts(pa); // get rid of any old points |
| 1200 |
pa = annAllocPts(n, dim); // allocate point storage |
| 1201 |
|
| 1202 |
switch (distr) { |
| 1203 |
case UNIFORM: // uniform over cube [-1,1]^d. |
| 1204 |
annUniformPts(pa, n, dim); |
| 1205 |
break; |
| 1206 |
case GAUSS: // Gaussian with mean 0 |
| 1207 |
annGaussPts(pa, n, dim, std_dev); |
| 1208 |
break; |
| 1209 |
case LAPLACE: // Laplacian, mean 0 and var 1 |
| 1210 |
annLaplacePts(pa, n, dim); |
| 1211 |
break; |
| 1212 |
case CO_GAUSS: // correlated Gaussian |
| 1213 |
annCoGaussPts(pa, n, dim, corr_coef); |
| 1214 |
break; |
| 1215 |
case CO_LAPLACE: // correlated Laplacian |
| 1216 |
annCoLaplacePts(pa, n, dim, corr_coef); |
| 1217 |
break; |
| 1218 |
case CLUS_GAUSS: // clustered Gaussian |
| 1219 |
annClusGaussPts(pa, n, dim, n_color, new_clust, std_dev); |
| 1220 |
break; |
| 1221 |
case CLUS_ORTH_FLATS: // clustered on orthog flats |
| 1222 |
annClusOrthFlats(pa, n, dim, n_color, new_clust, std_dev, max_dim); |
| 1223 |
break; |
| 1224 |
case CLUS_ELLIPSOIDS: // clustered ellipsoids |
| 1225 |
annClusEllipsoids(pa, n, dim, n_color, new_clust, std_dev, |
| 1226 |
std_dev_lo, std_dev_hi, max_dim); |
| 1227 |
break; |
| 1228 |
case PLANTED: // planted distribution |
| 1229 |
annPlanted(pa, n, dim, src, n_src, std_dev); |
| 1230 |
break; |
| 1231 |
default: |
| 1232 |
Error("INTERNAL ERROR: Unknown distribution", ANNabort); |
| 1233 |
break; |
| 1234 |
} |
| 1235 |
|
| 1236 |
if (stats > SILENT) { |
| 1237 |
if(type == DATA) cout << "[Generating Data Points:\n"; |
| 1238 |
else cout << "[Generating Query Points:\n"; |
| 1239 |
cout << " number = " << n << "\n"; |
| 1240 |
cout << " dim = " << dim << "\n"; |
| 1241 |
cout << " distribution = " << distr_table[distr] << "\n"; |
| 1242 |
if (annIdum < 0) |
| 1243 |
cout << " seed = " << annIdum << "\n"; |
| 1244 |
if (distr == GAUSS || distr == CLUS_GAUSS |
| 1245 |
|| distr == CLUS_ORTH_FLATS) |
| 1246 |
cout << " std_dev = " << std_dev << "\n"; |
| 1247 |
if (distr == CLUS_ELLIPSOIDS) { |
| 1248 |
cout << " std_dev = " << std_dev << " (small) \n"; |
| 1249 |
cout << " std_dev_lo = " << std_dev_lo << "\n"; |
| 1250 |
cout << " std_dev_hi = " << std_dev_hi << "\n"; |
| 1251 |
} |
| 1252 |
if (distr == CO_GAUSS || distr == CO_LAPLACE) |
| 1253 |
cout << " corr_coef = " << corr_coef << "\n"; |
| 1254 |
if (distr == CLUS_GAUSS || distr == CLUS_ORTH_FLATS |
| 1255 |
|| distr == CLUS_ELLIPSOIDS) { |
| 1256 |
cout << " colors = " << n_color << "\n"; |
| 1257 |
if (new_clust) |
| 1258 |
cout << " (cluster centers regenerated)\n"; |
| 1259 |
} |
| 1260 |
if (distr == CLUS_ORTH_FLATS || distr == CLUS_ELLIPSOIDS) { |
| 1261 |
cout << " max_dim = " << max_dim << "\n"; |
| 1262 |
} |
| 1263 |
} |
| 1264 |
// want to see points? |
| 1265 |
if ((type == DATA && stats >= SHOW_PTS) || |
| 1266 |
(type == QUERY && stats >= QUERY_RES)) { |
| 1267 |
if(type == DATA) cout << "(Data Points:\n"; |
| 1268 |
else cout << "(Query Points:\n"; |
| 1269 |
for (int i = 0; i < n; i++) { |
| 1270 |
cout << " " << setw(4) << i << "\t"; |
| 1271 |
printPoint(pa[i], dim); |
| 1272 |
cout << "\n"; |
| 1273 |
} |
| 1274 |
cout << " )\n"; |
| 1275 |
} |
| 1276 |
cout << "]\n"; |
| 1277 |
} |
| 1278 |
|
| 1279 |
//------------------------------------------------------------------------ |
| 1280 |
// readPts - read a collection of data or query points. |
| 1281 |
//------------------------------------------------------------------------ |
| 1282 |
|
| 1283 |
void readPts( |
| 1284 |
ANNpointArray &pa, // point array (returned) |
| 1285 |
int &n, // number of points |
| 1286 |
char *file_nm, // file name |
| 1287 |
PtType type) // point type (DATA, QUERY) |
| 1288 |
{ |
| 1289 |
int i; |
| 1290 |
//-------------------------------------------------------------------- |
| 1291 |
// Open input file and read points |
| 1292 |
//-------------------------------------------------------------------- |
| 1293 |
ifstream in_file(file_nm); // try to open data file |
| 1294 |
if (!in_file) { |
| 1295 |
cerr << "File name: " << file_nm << "\n"; |
| 1296 |
Error("Cannot open input data/query file", ANNabort); |
| 1297 |
} |
| 1298 |
// allocate storage for points |
| 1299 |
if (pa != NULL) annDeallocPts(pa); // get rid of old points |
| 1300 |
pa = annAllocPts(n, dim); |
| 1301 |
|
| 1302 |
for (i = 0; i < n; i++) { // read the data |
| 1303 |
if (!(in_file >> pa[i][0])) break; |
| 1304 |
for (int d = 1; d < dim; d++) { |
| 1305 |
in_file >> pa[i][d]; |
| 1306 |
} |
| 1307 |
} |
| 1308 |
|
| 1309 |
char ignore_me; // character for EOF test |
| 1310 |
in_file >> ignore_me; // try to get one more character |
| 1311 |
if (!in_file.eof()) { // exhausted space before eof |
| 1312 |
if (type == DATA) |
| 1313 |
Error("`data_size' too small. Input file truncated.", ANNwarn); |
| 1314 |
else |
| 1315 |
Error("`query_size' too small. Input file truncated.", ANNwarn); |
| 1316 |
} |
| 1317 |
n = i; // number of points read |
| 1318 |
|
| 1319 |
//-------------------------------------------------------------------- |
| 1320 |
// Print summary |
| 1321 |
//-------------------------------------------------------------------- |
| 1322 |
if (stats > SILENT) { |
| 1323 |
if (type == DATA) { |
| 1324 |
cout << "[Read Data Points:\n"; |
| 1325 |
cout << " data_size = " << n << "\n"; |
| 1326 |
} |
| 1327 |
else { |
| 1328 |
cout << "[Read Query Points:\n"; |
| 1329 |
cout << " query_size = " << n << "\n"; |
| 1330 |
} |
| 1331 |
cout << " file_name = " << file_nm << "\n"; |
| 1332 |
cout << " dim = " << dim << "\n"; |
| 1333 |
// print if results requested |
| 1334 |
if ((type == DATA && stats >= SHOW_PTS) || |
| 1335 |
(type == QUERY && stats >= QUERY_RES)) { |
| 1336 |
cout << " (Points:\n"; |
| 1337 |
for (i = 0; i < n; i++) { |
| 1338 |
cout << " " << i << "\t"; |
| 1339 |
printPoint(pa[i], dim); |
| 1340 |
cout << "\n"; |
| 1341 |
} |
| 1342 |
cout << " )\n"; |
| 1343 |
} |
| 1344 |
cout << "]\n"; |
| 1345 |
} |
| 1346 |
} |
| 1347 |
|
| 1348 |
//------------------------------------------------------------------------ |
| 1349 |
// getTrueNN |
| 1350 |
// Computes the true nearest neighbors. For purposes of validation, |
| 1351 |
// this intentionally done in a rather dumb (but safe way), by |
| 1352 |
// invoking the brute-force search. |
| 1353 |
// |
| 1354 |
// The number of true nearest neighbors is somewhat larger than |
| 1355 |
// the number of nearest neighbors. This is so that the validation |
| 1356 |
// can determine the expected difference in element ranks. |
| 1357 |
// |
| 1358 |
// This procedure is invoked just prior to running queries. Since |
| 1359 |
// the operation takes a long time, it is performed only if needed. |
| 1360 |
// In particular, once generated, it will be regenerated only if |
| 1361 |
// new query or data points are generated, or if the requested number |
| 1362 |
// of true near neighbors or approximate near neighbors has changed. |
| 1363 |
// |
| 1364 |
// To validate fixed-radius searching, we compute two counts, one |
| 1365 |
// with the original query radius (trueSqRadius) and the other with |
| 1366 |
// a radius shrunken by the error factor (minSqradius). We then |
| 1367 |
// check that the count of points inside the approximate range is |
| 1368 |
// between these two bounds. Because fixed-radius search is |
| 1369 |
// allowed to ignore points within the shrunken radius, we only |
| 1370 |
// compute exact neighbors within this smaller distance (for we |
| 1371 |
// cannot guarantee that we will even visit the other points). |
| 1372 |
//------------------------------------------------------------------------ |
| 1373 |
|
| 1374 |
void getTrueNN() // compute true nearest neighbors |
| 1375 |
{ |
| 1376 |
if (stats > SILENT) { |
| 1377 |
cout << "(Computing true nearest neighbors for validation. This may take time.)\n"; |
| 1378 |
} |
| 1379 |
// deallocate existing storage |
| 1380 |
if (true_nn_idx != NULL) delete [] true_nn_idx; |
| 1381 |
if (true_dists != NULL) delete [] true_dists; |
| 1382 |
if (min_pts_in_range != NULL) delete [] min_pts_in_range; |
| 1383 |
if (max_pts_in_range != NULL) delete [] max_pts_in_range; |
| 1384 |
|
| 1385 |
if (true_nn > data_size) { // can't get more nn than points |
| 1386 |
true_nn = data_size; |
| 1387 |
} |
| 1388 |
|
| 1389 |
// allocate true answer storage |
| 1390 |
true_nn_idx = new ANNidx[true_nn*query_size]; |
| 1391 |
true_dists = new ANNdist[true_nn*query_size]; |
| 1392 |
min_pts_in_range = new int[query_size]; |
| 1393 |
max_pts_in_range = new int[query_size]; |
| 1394 |
|
| 1395 |
ANNidxArray curr_nn_idx = true_nn_idx; // current locations in arrays |
| 1396 |
ANNdistArray curr_dists = true_dists; |
| 1397 |
|
| 1398 |
// allocate search structure |
| 1399 |
ANNbruteForce *the_brute = new ANNbruteForce(data_pts, data_size, dim); |
| 1400 |
// compute nearest neighbors |
| 1401 |
for (int i = 0; i < query_size; i++) { |
| 1402 |
if (radius_bound == 0) { // standard kNN search |
| 1403 |
the_brute->annkSearch( // compute true near neighbors |
| 1404 |
query_pts[i], // query point |
| 1405 |
true_nn, // number of nearest neighbors |
| 1406 |
curr_nn_idx, // where to put indices |
| 1407 |
curr_dists); // where to put distances |
| 1408 |
} |
| 1409 |
else { // fixed radius kNN search |
| 1410 |
// search radii limits |
| 1411 |
ANNdist trueSqRadius = ANN_POW(radius_bound); |
| 1412 |
ANNdist minSqRadius = ANN_POW(radius_bound / (1+epsilon)); |
| 1413 |
min_pts_in_range[i] = the_brute->annkFRSearch( |
| 1414 |
query_pts[i], // query point |
| 1415 |
minSqRadius, // shrunken search radius |
| 1416 |
true_nn, // number of near neighbors |
| 1417 |
curr_nn_idx, // nearest neighbors (returned) |
| 1418 |
curr_dists); // distance (returned) |
| 1419 |
max_pts_in_range[i] = the_brute->annkFRSearch( |
| 1420 |
query_pts[i], // query point |
| 1421 |
trueSqRadius, // true search radius |
| 1422 |
0, NULL, NULL); // (ignore kNN info) |
| 1423 |
} |
| 1424 |
curr_nn_idx += true_nn; // increment nn index pointer |
| 1425 |
curr_dists += true_nn; // increment nn dist pointer |
| 1426 |
} |
| 1427 |
delete the_brute; // delete brute-force struct |
| 1428 |
valid_dirty = ANNfalse; // validation good for now |
| 1429 |
} |
| 1430 |
|
| 1431 |
//------------------------------------------------------------------------ |
| 1432 |
// doValidation |
| 1433 |
// Compares the approximate answers to the k-nearest neighbors |
| 1434 |
// against the true nearest neighbors (computed earlier). It is |
| 1435 |
// assumed that the true nearest neighbors and indices have been |
| 1436 |
// computed earlier. |
| 1437 |
// |
| 1438 |
// First, we check that all the results are within their allowed |
| 1439 |
// limits, and generate an internal error, if not. For the sake of |
| 1440 |
// performance evaluation, we also compute the following two |
| 1441 |
// quantities for nearest neighbors: |
| 1442 |
// |
| 1443 |
// Average Error |
| 1444 |
// ------------- |
| 1445 |
// The relative error between the distance to a reported nearest |
| 1446 |
// neighbor and the true nearest neighbor (of the same rank), |
| 1447 |
// |
| 1448 |
// Rank Error |
| 1449 |
// ---------- |
| 1450 |
// The difference in rank between the reported nearest neighbor and |
| 1451 |
// its position (if any) among the true nearest neighbors. If we |
| 1452 |
// cannot find this point among the true nearest neighbors, then |
| 1453 |
// it assumed that the rank of the true nearest neighbor is true_nn+1. |
| 1454 |
// |
| 1455 |
// Because of the possibility of duplicate distances, this is computed |
| 1456 |
// as follows. For the j-th reported nearest neighbor, we count the |
| 1457 |
// number of true nearest neighbors that are at least this close. Let |
| 1458 |
// this be rnk. Then the rank error is max(0, j-rnk). (In the code |
| 1459 |
// below, j is an array index and so the first item is 0, not 1. Thus |
| 1460 |
// we take max(0, j+1-rnk) instead.) |
| 1461 |
// |
| 1462 |
// For the results of fixed-radious range count, we verify that the |
| 1463 |
// reported number of points in the range lies between the actual |
| 1464 |
// number of points in the shrunken and the true search radius. |
| 1465 |
//------------------------------------------------------------------------ |
| 1466 |
|
| 1467 |
void doValidation() // perform validation |
| 1468 |
{ |
| 1469 |
int* curr_apx_idx = apx_nn_idx; // approx index pointer |
| 1470 |
ANNdistArray curr_apx_dst = apx_dists; // approx distance pointer |
| 1471 |
int* curr_tru_idx = true_nn_idx; // true index pointer |
| 1472 |
ANNdistArray curr_tru_dst = true_dists; // true distance pointer |
| 1473 |
int i, j; |
| 1474 |
|
| 1475 |
if (true_nn < near_neigh) { |
| 1476 |
Error("Cannot validate with fewer true near neighbors than actual", ANNabort); |
| 1477 |
} |
| 1478 |
|
| 1479 |
for (i = 0; i < query_size; i++) { // validate each query |
| 1480 |
//---------------------------------------------------------------- |
| 1481 |
// Compute result errors |
| 1482 |
// In fixed radius search it is possible that not all k |
| 1483 |
// nearest neighbors were computed. Because the true |
| 1484 |
// results are computed over the shrunken radius, we should |
| 1485 |
// have at least as many true nearest neighbors as |
| 1486 |
// approximate nearest neighbors. (If not, an infinite |
| 1487 |
// error will be generated, and so an internal error will |
| 1488 |
// will be generated. |
| 1489 |
// |
| 1490 |
// Because nearest neighbors are sorted in increasing order |
| 1491 |
// of distance, as soon as we see a null index, we can |
| 1492 |
// terminate the distance checking. The error in the |
| 1493 |
// result should not exceed epsilon. However, if |
| 1494 |
// max_pts_visit is nonzero (meaning that the search is |
| 1495 |
// terminated early) this might happen. |
| 1496 |
//---------------------------------------------------------------- |
| 1497 |
for (j = 0; j < near_neigh; j++) { |
| 1498 |
if (curr_tru_idx[j] == ANN_NULL_IDX)// no more true neighbors? |
| 1499 |
break; |
| 1500 |
// true i-th smallest distance |
| 1501 |
double true_dist = ANN_ROOT(curr_tru_dst[j]); |
| 1502 |
// reported i-th smallest |
| 1503 |
double rept_dist = ANN_ROOT(curr_apx_dst[j]); |
| 1504 |
// better than optimum? |
| 1505 |
if (rept_dist < true_dist*(1-ERR)) { |
| 1506 |
Error("INTERNAL ERROR: True nearest neighbor incorrect", |
| 1507 |
ANNabort); |
| 1508 |
} |
| 1509 |
|
| 1510 |
double resultErr; // result error |
| 1511 |
if (true_dist == 0.0) { // let's not divide by zero |
| 1512 |
if (rept_dist != 0.0) resultErr = ANN_DBL_MAX; |
| 1513 |
else resultErr = 0.0; |
| 1514 |
} |
| 1515 |
else { |
| 1516 |
resultErr = (rept_dist - true_dist) / ((double) true_dist); |
| 1517 |
} |
| 1518 |
|
| 1519 |
if (resultErr > epsilon + RND_OFF && max_pts_visit == 0) { |
| 1520 |
Error("INTERNAL ERROR: Actual error exceeds epsilon", |
| 1521 |
ANNabort); |
| 1522 |
} |
| 1523 |
#ifdef ANN_PERF |
| 1524 |
ann_average_err += resultErr; // update statistics error |
| 1525 |
#endif |
| 1526 |
} |
| 1527 |
//-------------------------------------------------------------------- |
| 1528 |
// Compute rank errors (only needed for perf measurements) |
| 1529 |
//-------------------------------------------------------------------- |
| 1530 |
#ifdef ANN_PERF |
| 1531 |
for (j = 0; j < near_neigh; j++) { |
| 1532 |
if (curr_tru_idx[i] == ANN_NULL_IDX) // no more true neighbors? |
| 1533 |
break; |
| 1534 |
|
| 1535 |
double rnkErr = 0.0; // rank error |
| 1536 |
// reported j-th distance |
| 1537 |
ANNdist rept_dist = curr_apx_dst[j]; |
| 1538 |
int rnk = 0; // compute rank of this item |
| 1539 |
while (rnk < true_nn && curr_tru_dst[rnk] <= rept_dist) |
| 1540 |
rnk++; |
| 1541 |
if (j+1-rnk > 0) rnkErr = (double) (j+1-rnk); |
| 1542 |
ann_rank_err += rnkErr; // update average rank error |
| 1543 |
} |
| 1544 |
#endif |
| 1545 |
//---------------------------------------------------------------- |
| 1546 |
// Check range counts from fixed-radius query |
| 1547 |
//---------------------------------------------------------------- |
| 1548 |
if (radius_bound != 0) { // fixed-radius search |
| 1549 |
if (apx_pts_in_range[i] < min_pts_in_range[i] || |
| 1550 |
apx_pts_in_range[i] > max_pts_in_range[i]) |
| 1551 |
Error("INTERNAL ERROR: Invalid fixed-radius range count", |
| 1552 |
ANNabort); |
| 1553 |
} |
| 1554 |
|
| 1555 |
curr_apx_idx += near_neigh; |
| 1556 |
curr_apx_dst += near_neigh; |
| 1557 |
curr_tru_idx += true_nn; // increment current pointers |
| 1558 |
curr_tru_dst += true_nn; |
| 1559 |
} |
| 1560 |
} |
| 1561 |
|
| 1562 |
//---------------------------------------------------------------------- |
| 1563 |
// treeStats |
| 1564 |
// Computes a number of statistics related to kd_trees and |
| 1565 |
// bd_trees. These statistics are printed if in verbose mode, |
| 1566 |
// and otherwise they are only printed if they are deemed to |
| 1567 |
// be outside of reasonable operating bounds. |
| 1568 |
//---------------------------------------------------------------------- |
| 1569 |
|
| 1570 |
#define log2(x) (log(x)/log(2.0)) // log base 2 |
| 1571 |
|
| 1572 |
void treeStats( |
| 1573 |
ostream &out, // output stream |
| 1574 |
ANNbool verbose) // print stats |
| 1575 |
{ |
| 1576 |
const int MIN_PTS = 20; // min no. pts for checking |
| 1577 |
const float MAX_FRAC_TL = 0.50; // max frac of triv leaves |
| 1578 |
const float MAX_AVG_AR = 20; // max average aspect ratio |
| 1579 |
|
| 1580 |
ANNkdStats st; // statistics structure |
| 1581 |
|
| 1582 |
the_tree->getStats(st); // get statistics |
| 1583 |
// total number of nodes |
| 1584 |
int n_nodes = st.n_lf + st.n_spl + st.n_shr; |
| 1585 |
// should be O(n/bs) |
| 1586 |
int opt_n_nodes = (int) (2*(float(st.n_pts)/st.bkt_size)); |
| 1587 |
int too_many_nodes = 10*opt_n_nodes; |
| 1588 |
if (st.n_pts >= MIN_PTS && n_nodes > too_many_nodes) { |
| 1589 |
out << "-----------------------------------------------------------\n"; |
| 1590 |
out << "Warning: The tree has more than 10x as many nodes as points.\n"; |
| 1591 |
out << "You may want to consider a different split or shrink method.\n"; |
| 1592 |
out << "-----------------------------------------------------------\n"; |
| 1593 |
verbose = ANNtrue; |
| 1594 |
} |
| 1595 |
// fraction of trivial leaves |
| 1596 |
float frac_tl = (st.n_lf == 0 ? 0 : ((float) st.n_tl)/ st.n_lf); |
| 1597 |
if (st.n_pts >= MIN_PTS && frac_tl > MAX_FRAC_TL) { |
| 1598 |
out << "-----------------------------------------------------------\n"; |
| 1599 |
out << "Warning: A significant fraction of leaves contain no points.\n"; |
| 1600 |
out << "You may want to consider a different split or shrink method.\n"; |
| 1601 |
out << "-----------------------------------------------------------\n"; |
| 1602 |
verbose = ANNtrue; |
| 1603 |
} |
| 1604 |
// depth should be O(dim*log n) |
| 1605 |
int too_many_levels = (int) (2.0 * st.dim * log2((double) st.n_pts)); |
| 1606 |
int opt_levels = (int) log2(double(st.n_pts)/st.bkt_size); |
| 1607 |
if (st.n_pts >= MIN_PTS && st.depth > too_many_levels) { |
| 1608 |
out << "-----------------------------------------------------------\n"; |
| 1609 |
out << "Warning: The tree is more than 2x as deep as (dim*log n).\n"; |
| 1610 |
out << "You may want to consider a different split or shrink method.\n"; |
| 1611 |
out << "-----------------------------------------------------------\n"; |
| 1612 |
verbose = ANNtrue; |
| 1613 |
} |
| 1614 |
// average leaf aspect ratio |
| 1615 |
if (st.n_pts >= MIN_PTS && st.avg_ar > MAX_AVG_AR) { |
| 1616 |
out << "-----------------------------------------------------------\n"; |
| 1617 |
out << "Warning: Average aspect ratio of cells is quite large.\n"; |
| 1618 |
out << "This may slow queries depending on the point distribution.\n"; |
| 1619 |
out << "-----------------------------------------------------------\n"; |
| 1620 |
verbose = ANNtrue; |
| 1621 |
} |
| 1622 |
|
| 1623 |
//------------------------------------------------------------------ |
| 1624 |
// Print summaries if requested |
| 1625 |
//------------------------------------------------------------------ |
| 1626 |
if (verbose) { // output statistics |
| 1627 |
out << " (Structure Statistics:\n"; |
| 1628 |
out << " n_nodes = " << n_nodes |
| 1629 |
<< " (opt = " << opt_n_nodes |
| 1630 |
<< ", best if < " << too_many_nodes << ")\n" |
| 1631 |
<< " n_leaves = " << st.n_lf |
| 1632 |
<< " (" << st.n_tl << " contain no points)\n" |
| 1633 |
<< " n_splits = " << st.n_spl << "\n" |
| 1634 |
<< " n_shrinks = " << st.n_shr << "\n"; |
| 1635 |
out << " empty_leaves = " << frac_tl*100 |
| 1636 |
<< " percent (best if < " << MAX_FRAC_TL*100 << " percent)\n"; |
| 1637 |
out << " depth = " << st.depth |
| 1638 |
<< " (opt = " << opt_levels |
| 1639 |
<< ", best if < " << too_many_levels << ")\n"; |
| 1640 |
out << " avg_aspect_ratio = " << st.avg_ar |
| 1641 |
<< " (best if < " << MAX_AVG_AR << ")\n"; |
| 1642 |
out << " )\n"; |
| 1643 |
} |
| 1644 |
} |