mvptree

Mvptree (estrutura de dados de árvores de ponto de vista múltiplo)

Uma estrutura de dados baseada em distância para a indexação de dados multidimensionais. O MVPTree indexa objetos vetoriais de acordo com sua distância de pontos de vista selecionados escolhidos diretamente a partir dos dados indexados.

Testes de desempenho

Os testes a seguir medem os tempos de construção e consulta para vários tamanhos de índice. Os pontos de dados são objeto vetorial de valor real 16-dimensional (uniforme distribuído independentemente). As operações de construção refletem o número de operações de distância necessárias para construir a árvore. Da mesma forma, as operações de consulta são o número médio de operações de distância para consultar o índice para um raio constante de 0,04. As operações de construção e consulta são normalizadas para o tamanho da árvore e expressas como uma porcentagem. Cada linha no gráfico é a média de 5 testes, onde a estrutura da árvore é construída, consultada para 10 aglomerados de 10 pontos e depois retirada.

N	Mem	Construa Opers	Construir tempo	Opers de consulta	Tempo de consulta
100k	122 MB	2554%	21,4μs	0,0087%	42,4μs
200k	289 MB	2693%	26,3μs	0,0048%	63,4μs
400K	548 MB	2792%	36,8μs	0,0022%	70,2μs
800K	963MB	2872%	59,4μs	0,0012%	86,0μs
1m	1,1 GB	2899%	62,9μs	0,0010%	107μs
2m	2,7 GB	3021%	79,6μs	0,0005%	163μs
4m	5,5 GB	3139%	101μs	0,0002%	242μs

Aqui estão as estatísticas de consulta para vários tamanhos de raio e um tamanho de índice constante de n = 1.000.000:

raio	Opers de consulta.	Tempo 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 experimentar por si mesmo, execute o programa de teste, runmvptree2 . Você pode mexer com os parâmetros de teste no arquivo, tests/run_mvptree2.cpp.

Programação

Use os arquivos de cabeçalho do modelo. Primeiro, crie um tipo de dados personalizado. Exemplos são fornecidos em 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);
	}
	
};

O tipo de dados personalizado deve fornecer o contutor de cópia, o operador de atribuição e a implementação da função de distância.

Em seguida, use a classe modelada:

 #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 mais detalhes, consulte os programas no diretório de testes.

Instalar

 cmake .
make
make test
make install