Modified the scan kernel so that it can work with > 1024*1024 numbers
[RBC.git] / readme.txt
1 ***Random Ball Cover (RBC)***
2 Lawrence Cayton
3 lcayton@tuebingen.mpg.de
4
5 (C) Copyright 2010, Lawrence Cayton
6
7 This program is free software: you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation, either version 3 of the License, or
10 (at your option) any later version.
11
12 This program is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with this program. If not, see <http://www.gnu.org/licenses/>.
19
20 ---------------------------------------------------------------------
21
22 This is a C and CUDA implementation of the Random Ball Cover data
23 structure for nearest neighbor search.
24
25 Notes on the code:
26 * The code requires that the entire DB and query set fit into the
27 device memory.
28
29 * For the most part, device variables (ie arrays residing on the GPU)
30 begin with a lowercase d. For example, the device version of the
31 DB variable x is dx.
32
33 * The computePlan code is a bit more complex than is needed for the
34 version of the RBC search algorithm described in the paper. The
35 search algorithm described in the paper has two steps: (1) Find the
36 closest representative to the query. (2) Explore the points owned
37 by that representative (ie the s-closest points to the representative
38 in the DB). The computePlan code is more complex to make it easy
39 to try out other options. For example, one could search the points
40 owned by the *two* closest representatives to the query instead. This
41 would require only minor changes to the code.
42
43 * Currently the software works only in single precision. If you wish
44 to switch to double precision, you must edit the defs.h file. Simply
45 uncomment the lines
46
47 typedef double real;
48 #define MAX_REAL DBL_MAX
49
50 and comment out the lines
51
52 typedef float real;
53 #define MAX_REAL FLT_MAX
54
55 Then, you must do a
56
57 make clean
58
59 followed by another make.
60
61 * This software has been tested on the following graphics cards:
62 NVIDIA GTX 285
63 NVIDIA Tesla c2050.
64
65 * This sotware has been tested under the following software setup:
66 Ubuntu 9.10 (linux)
67 gcc 4.4
68 cuda 3.1
69
70 Please share your experience getting it to work under Windows and
71 Mac OSX!
72
73