Functions
bool	setProfilingFlag (int argc, char **argv)
	Checks the command line arguments for the profiling flag, `--profiling`. More...

template<typename T >
uint64_t	nextPow2 (T num)
	Returns the first power of 2 greater than or equal to the input. More...

template<typename T >
void	printBuffer (const char title, T ptr, uint32_t width, uint32_t height)
	Prints an array of an integer type to standard output. More...

template<typename T >
void	printBufferF (const char title, T ptr, uint32_t width, uint32_t height, uint32_t prec)
	Prints an array of floating-point type to standard output. More...

template<typename T >
void	cpuReduce (T in, T out, uint32_t cols, uint32_t rows, std::function< bool(T, T)> func)
	Reduces each row of an array to a single element. More...

template<typename T >
void	cpuInScan (T in, T out, uint32_t width, uint32_t height)
	Performs an inclusive scan operation on the columns of an array. More...

template<typename T >
void	cpuExScan (T in, T out, uint32_t width, uint32_t height)
	Performs an exclusive scan operation on the columns of an array. More...

template<typename T >
void	cpuRBCComputeDists (T X, T R, T *D, uint32_t nx, uint32_t nr, uint32_t d)
	Computes the distances between two sets of points in a brute force way. More...

template<typename T >
void	cpuRBCComputeDists8 (T X, T R, T *D, uint32_t nx, uint32_t nr, uint32_t d, T a)
	Computes the distances between two sets of points in a brute force way. More...

template<typename T >
void	cpuRBCMinDists (T in, rbc_dist_id out, uint32_t N, uint32_t Rnk, uint32_t cols, uint32_t rows, bool accCounters)
	Computes the minimum element, and its corresponding column id, for each row in an array. It also builds a histogram of the id values. And lastly, it stores the rank (order of insert) of each minimum element within its corresponding histogram bin. More...

template<typename T >
void	cpuRBCPermute (T X, rbc_dist_id ID, T Xp, rbc_dist_id IDp, uint32_t O, uint32_t Rnk, uint32_t nx, uint32_t nr, uint32_t d, bool permID)
	Performs a permutation of the `RBC` database to form the representative lists. More...

template<typename T >
T	euclideanMetric (T p1, T p2, uint32_t d)
	Calculates the euclidean distance betweeen two points. More...

template<typename T >
T	euclideanMetric8Squared (T p1, T p2, float a)
	Calculates the euclidean distance betweeen two points in \( \mathbb{R}^8 \).. More...

template<typename T >
void	cpuRBCSearch (T Qp, rbc_dist_id RID, T Xp, cl_uint O, cl_uint N, rbc_dist_id NNID, T *NN, uint32_t nq, uint32_t nr, uint32_t nx, uint32_t d)
	Uses the RBC data structure to search for the nearest neighbors. More...

template<typename T >
void	cpuRBCSearch8 (T Qp, rbc_dist_id RID, T Xp, cl_uint O, cl_uint N, rbc_dist_id NNID, T *NN, uint32_t nq, uint32_t nr, uint32_t nx, T a)
	Uses the RBC data structure to search for the nearest neighbors. More...

template<typename T >
void	cpuNNSearch (T Q, T X, T *NN, uint32_t nq, uint32_t nx, uint32_t d)
	Computes (brute force) the nearest neighbors of a set of queries. More...

template<typename T >
T	meanError (T Q, T NN, uint32_t n, uint32_t d)
	Computes the mean euclidean distance from the queries to their NNs. More...

Variables
std::function< unsigned char()>	rNum_0_255 = std::bind (distribution1, generator)
	Uniform number generator in the range \([0, 255]\). More...

std::function< unsigned short()>	rNum_0_10000 = std::bind (distribution2, generator)
	Uniform number generator in the range \([0, 10000]\). More...

std::function< float()>	rNum_R_0_1 = std::bind (distributionR1, generator)
	Uniform number generator in the range \([0.0, 1.0)\). More...

std::function< float()>	rNum_R_1_255_E__6 = std::bind (distributionR2, generator)
	Uniform number generator in the range \([1e-6, 255*1e-6)\). More...

Function Documentation

template<typename T >

void RBC::cpuExScan	(	T *	in,
		T *	out,
		uint32_t	width,
		uint32_t	height
	)

Performs an exclusive scan operation on the columns of an array.

It is just a naive serial implementation.

Template Parameters

T	type of the data to be handled.

Parameters

[in]	in	input data.
[out]	out	output (scan) data.
[in]	width	width of the array.
[in]	height	height of the array.

template<typename T >

void RBC::cpuInScan	(	T *	in,
		T *	out,
		uint32_t	width,
		uint32_t	height
	)

Performs an inclusive scan operation on the columns of an array.

It is just a naive serial implementation.

Template Parameters

T	type of the data to be handled.

Parameters

[in]	in	input data.
[out]	out	output (scan) data.
[in]	width	width of the array.
[in]	height	height of the array.

template<typename T >

void RBC::cpuNNSearch	(	T *	Q,
		T *	X,
		T *	NN,
		uint32_t	nq,
		uint32_t	nx,
		uint32_t	d
	)

Computes (brute force) the nearest neighbors of a set of queries.

It is just a naive serial implementation.

Template Parameters

T	type of the data to be handled.

Parameters

[in]	Q	array of query points (each row contains a point).
[in]	X	array of database points (each row contains a point).
[out]	NN	array of NN points (each row contains a point).
[in]	nq	number of query points.
[in]	nx	number of database points.
[in]	d	dimensionality of the associated points.

template<typename T >

void RBC::cpuRBCComputeDists	(	T *	X,
		T *	R,
		T *	D,
		uint32_t	nx,
		uint32_t	nr,
		uint32_t	d
	)

Computes the distances between two sets of points in a brute force way.

It is just a naive serial implementation.

Parameters

[in]	X	array of the database points (each row contains a point).
[in]	R	array of the representative points (each row contains a point).
[out]	D	array of distances of the database points from the representative points (each row contains the distances of a database point from all the representative points)
[in]	nx	number of database points.
[in]	nr	number of representative points.
[in]	d	dimensionality of the associated points.

template<typename T >

void RBC::cpuRBCComputeDists8	(	T *	X,
		T *	R,
		T *	D,
		uint32_t	nx,
		uint32_t	nr,
		uint32_t	d,
		T	a
	)

Computes the distances between two sets of points in a brute force way.

It is just a naive serial implementation.

Parameters

[in]	X	array of the database points (each row contains a point).
[in]	R	array of the representative points (each row contains a point).
[out]	D	array of distances of the database points from the representative points (each row contains the distances of a database point from all the representative points)
[in]	nx	number of database points.
[in]	nr	number of representative points.
[in]	d	dimensionality of the associated points.
[in]	a	scaling factor for the geometric and photometric parts.

template<typename T >

void RBC::cpuRBCMinDists	(	T *	in,
		rbc_dist_id *	out,
		uint32_t *	N,
		uint32_t *	Rnk,
		uint32_t	cols,
		uint32_t	rows,
		bool	accCounters
	)

Computes the minimum element, and its corresponding column id, for each row in an array. It also builds a histogram of the id values. And lastly, it stores the rank (order of insert) of each minimum element within its corresponding histogram bin.

It is just a naive serial implementation.

Parameters

[in]	in	input data.
[out]	out	output (reduced) data (min and column id).
[out]	N	array with the representative list cardinalities.
[out]	Rnk	array with the indices of each database point within the associated list.
[in]	cols	number of columns in the input array.
[in]	rows	number of rows in the input array.
[in]	accCounters	a flag to indicate whether or not to involve in the computation the list element counters, `N`, and element ranks, `Rnk`.

template<typename T >

void RBC::cpuRBCPermute	(	T *	X,
		rbc_dist_id *	ID,
		T *	Xp,
		rbc_dist_id *	IDp,
		uint32_t *	O,
		uint32_t *	Rnk,
		uint32_t	nx,
		uint32_t	nr,
		uint32_t	d,
		bool	permID
	)

Performs a permutation of the RBC database to form the representative lists.

It is just a naive serial implementation.

Template Parameters

T	type of the data to be handled.

Parameters

[in]	X	array of database points (each row contains a point).
[in]	ID	array with the minimum distances and representative ids per database point.
[out]	Xp	permuted database.
[out]	IDp	array with the minimum distances and representative ids per database point in Xp.
[in]	O	array containing the index (offset) of the first element of each representative list within the database.
[in]	Rnk	array containing the rank (aka order, index) of each database point within the associated representative list.
[in]	nx	number of database points.
[in]	nr	number of representative points.
[in]	d	dimensionality of the associated points.
[in]	permID	flag to indicate whether or not to also permute the ID array.

template<typename T >

void RBC::cpuRBCSearch	(	T *	Qp,
		rbc_dist_id *	RID,
		T *	Xp,
		cl_uint *	O,
		cl_uint *	N,
		rbc_dist_id *	NNID,
		T *	NN,
		uint32_t	nq,
		uint32_t	nr,
		uint32_t	nx,
		uint32_t	d
	)

Uses the RBC data structure to search for the nearest neighbors.

It is just a naive serial implementation.

Template Parameters

T	type of the data to be handled.

Parameters

[in]	Qp	permuted array of query points (each row contains a point).
[in]	RID	array with minimum distances and representative ids per query point in Qp.
[in]	Xp	permuted array of database points (each row contains a point).
[in]	O	array containing the index (offset) of the first element of each representative list within the database.
[in]	N	array with the representative list cardinalities.
[out]	NNID	array with distances and NN ids for each query point.
[out]	NN	array of NN points (each row contains a point).
[in]	nq	number of query points.
[in]	nr	number of representative points.
[in]	nx	number of database points.
[in]	d	dimensionality of the associated points.

template<typename T >

void RBC::cpuRBCSearch8	(	T *	Qp,
		rbc_dist_id *	RID,
		T *	Xp,
		cl_uint *	O,
		cl_uint *	N,
		rbc_dist_id *	NNID,
		T *	NN,
		uint32_t	nq,
		uint32_t	nr,
		uint32_t	nx,
		T	a
	)

Uses the RBC data structure to search for the nearest neighbors.

It is just a naive serial implementation.

Template Parameters

T	type of the data to be handled.

Parameters

[in]	Qp	permuted array of query points (each row contains a point).
[in]	RID	array with minimum distances and representative ids per query point in Qp.
[in]	Xp	permuted array of database points (each row contains a point).
[in]	O	array containing the index (offset) of the first element of each representative list within the database.
[in]	N	array with the representative list cardinalities.
[out]	NNID	array with distances and NN ids for each query point.
[out]	NN	array of NN points (each row contains a point).
[in]	nq	number of query points.
[in]	nr	number of representative points.
[in]	nx	number of database points.
[in]	a	scaling factor multiplying the result of the distance calculation for the `high` part of the points (`cl_float8` vectors).

template<typename T >

void RBC::cpuReduce	(	T *	in,
		T *	out,
		uint32_t	cols,
		uint32_t	rows,
		std::function< bool(T, T)>	func
	)

Reduces each row of an array to a single element.

It is just a naive serial implementation.

Parameters

[in]	in	input data.
[out]	out	output (reduced) data.
[in]	cols	number of columns in the input array.
[in]	rows	number of rows in the input array.
[in]	func	function supporting the requested operation.

template<typename T >

T RBC::euclideanMetric	(	T *	p1,
		T *	p2,
		uint32_t	d
	)

Calculates the euclidean distance betweeen two points.

It is just a naive serial implementation.

Template Parameters

T	type of the data to be handled.

Parameters

[in]	p1	first point.
[in]	p2	second point.
[in]	d	dimensionality of the associated points.

template<typename T >

T RBC::euclideanMetric8Squared	(	T *	p1,
		T *	p2,
		float	a
	)

Calculates the euclidean distance betweeen two points in \( \mathbb{R}^8 \)..

It is just a naive serial implementation.

Template Parameters

T	type of the data to be handled.

Parameters

[in]	p1	first point.
[in]	p2	second point.
[in]	a	scaling factor multiplying the result of the distance calculation for the `high` part of the points (`cl_float8` vectors).

template<typename T >

T RBC::meanError	(	T *	Q,
		T *	NN,
		uint32_t	n,
		uint32_t	d
	)

Computes the mean euclidean distance from the queries to their NNs.

It is just a naive serial implementation.

Template Parameters

T	type of the data to be handled.

Parameters

[in]	Q	array of queries (each row contains a point).
[in]	NN	array of NNs (each row contains a point).
[in]	n	number of points in the arrays.
[in]	d	dimensionality of the associated points.

template<typename T >

uint64_t RBC::nextPow2 ( T num )

Returns the first power of 2 greater than or equal to the input.

Parameters

[in] num input data.

Returns: The first power of 2 >= num.

template<typename T >

void RBC::printBuffer	(	const char *	title,
		T *	ptr,
		uint32_t	width,
		uint32_t	height
	)

Prints an array of an integer type to standard output.

Template Parameters

T	type of the data to be printed.

Parameters

[in]	title	legend for the output.
[in]	ptr	array that is to be displayed.
[in]	width	width of the array.
[in]	height	height of the array.

template<typename T >

void RBC::printBufferF	(	const char *	title,
		T *	ptr,
		uint32_t	width,
		uint32_t	height,
		uint32_t	prec
	)

Prints an array of floating-point type to standard output.

Template Parameters

T	type of the data to be printed.

Parameters

[in]	title	legend for the output.
[in]	ptr	array that is to be displayed.
[in]	width	width of the array.
[in]	height	height of the array.
[in]	prec	the number of decimal places to print.

bool RBC::setProfilingFlag	(	int	argc,
		char **	argv
	)

Checks the command line arguments for the profiling flag, --profiling.

Parameters

[in]	argc	command line argument count
[in]	argv	command line arguments

Returns: A flag to indicate whether a command line argument for profiling was provided.

Variable Documentation

std::function< unsigned short()> RBC::rNum_0_10000 = std::bind (distribution2, generator)

Uniform number generator in the range \([0, 10000]\).

std::function< unsigned char()> RBC::rNum_0_255 = std::bind (distribution1, generator)

Uniform number generator in the range \([0, 255]\).

std::function< float()> RBC::rNum_R_0_1 = std::bind (distributionR1, generator)

Uniform number generator in the range \([0.0, 1.0)\).

std::function< float()> RBC::rNum_R_1_255_E__6 = std::bind (distributionR2, generator)

Uniform number generator in the range \([1e-6, 255*1e-6)\).

Functions

Variables

Function Documentation

Variable Documentation