mvptree

MVPTree (estructura de datos de árboles de punto de vista múltiple)

Una estructura de datos basada en la distancia para la indexación de datos multidimensionales. El MVPTree indexa los objetos vectoriales de acuerdo con su distancia de los puntos de vista seleccionados elegidos directamente de los datos indexados.

Pruebas de rendimiento

Las siguientes pruebas miden los tiempos de construcción y consulta para varios tamaños de índice. Los puntos de datos son objeto vectorial de valor real 16 dimensional (uniforme distribuido independientemente). Las operaciones de compilación reflejan el número de operaciones de distancia necesarias para construir el árbol. Del mismo modo, las operaciones de consulta son el número promedio de operaciones de distancia para consultar el índice para un radio constante de 0.04. Las operaciones de construcción y consulta se normalizan al tamaño del árbol y se expresan como un porcentaje. Cada línea en la tabla es el promedio de 5 corrientes de prueba, donde se construye la estructura del árbol, se consulta por 10 grupos de 10 puntos y luego se retiró.

norte	Memorando	Construir	Tiempo de construcción	Operación de consulta	Tiempo de consulta
100k	122 MB	2554%	21.4 μs	0.0087%	42.4 μs
200K	289MB	2693%	26.3 μs	0.0048%	63.4 μs
400k	548mb	2792%	36.8 μs	0.0022%	70.2 μs
800k	963MB	2872%	59.4 μs	0.0012%	86.0 μs
1M	1.1GB	2899%	62.9 μs	0.0010%	107 μs
2m	2.7GB	3021%	79.6 μs	0.0005%	163 μs
4m	5.5 GB	3139%	101 μs	0.0002%	242 μs

Aquí están las estadísticas de consulta para varios tamaños de radio y un tamaño de índice constante de n = 1,000,000:

radio	Consulta Opers.	Tiempo de consulta
0.02	0.00094%	30.9 μs
0.04	0.00092%	121 μs
0.06	0.0012%	359 μs
0.08	0.00041%	971 μs
0.10	0.0241%	2.67 μs

Para probarlo usted mismo, ejecute el programa de prueba, runmvptree2 . Puede jugar con los parámetros de prueba en el archivo, pruebas/run_mvptree2.cpp.

Programación

Use los archivos de encabezado de plantilla. Primero, cree un tipo de datos personalizado. Se proporcionan ejemplos bajo Key.HPP:

 struct VectorKeyObject {
	double key[16];
	VectorKeyObject(){};
	VectorKeyObject(const double otherkey[]){
		for (int i=0;i < 16;i++) key[i] = otherkey[i];
	}
	VectorKeyObject(const VectorKeyObject &other){
		for (int i=0;i < 16;i++) key[i] = other.key[i];
	}
	const VectorKeyObject& operator=(const VectorKeyObject &other){
		for (int i=0;i < 16;i++) key[i] = other.key[i];
		return *this;
	}
	const double distance(const VectorKeyObject &other)const {
		double sum = 0;
		for (int i=0;i < 16;i++){
			sum += pow(key[i] - other.key[i], 2.0);
		}
		return sqrt(sum/16.0);
	}
	
};

El tipo de datos personalizado debe proporcionar el Contructor de copias, el operador de asignación y la implementación de la función de distancia.

A continuación, use la clase plantada:

 #include "mvptree/mvptree.hpp"


MVPTree<VectorKeyObject> mvptree;

vector<VectorKeyObject> points;

mvptree.Add(points);
mvptree.Sync();

int sz = mvptree.Size();
assert(sz == points.size());


VectorKeyObject target;
double radius = ...  //  value for data set 
vector<item_t<VectorKeyObject>> results = mvptree.Query(target, radius);


mvptree.Clear();
sz = mvptree.Size();
assert(sz == 0);

Para obtener más detalles, consulte los programas en el directorio de pruebas.

Instalar

 cmake .
make
make test
make install