mvptree

MVPTREE (Structure de données de l'arborescence multiple de point de vue)

Une structure de données basée sur la distance pour l'indexation des données multidimensionnelles. Le MVPTREE index des objets vectoriels en fonction de sa distance de sélectionner les points de vue choisis directement dans les données indexées.

Tests de performance

Les tests suivants mesurent les temps de construction et de requête pour diverses tailles d'index. Les points de données sont un objet vectoriel à valeur réel à 16 dimensions (uniforme indépendamment distribué). Les opérations de construction reflètent le nombre d'opérations de distance nécessaires pour construire l'arbre. De même, les opérations de requête sont le nombre moyen d'opérations de distance pour interroger l'indice pour un rayon constant de 0,04. Les opérations de construction et de requête sont normalisées à la taille de l'arbre et exprimées en pourcentage. Chaque ligne du graphique est la moyenne de 5 essais, où la structure des arbres est construite, interrogée pour 10 grappes de 10 points, puis retirée.

N	Mem	Construire des oper	Du temps de construction	OPERS QUERY	Temps de requête
100k	122 Mo	2554%	21,4 μs	0,0087%	42,4 μs
200K	289 Mo	2693%	26,3 μs	0,0048%	63,4 μs
400k	548 Mo	2792%	36,8 μs	0,0022%	70,2 μs
800k	963 Mo	2872%	59,4 μs	0,0012%	86,0 μs
1m	1,1 Go	2899%	62,9 μs	0,0010%	107μs
2m	2,7 Go	3021%	79,6 μs	0,0005%	163 μs
4m	5,5 Go	3139%	101 μs	0,0002%	242 μs

Voici les statistiques de requête pour diverses tailles de rayon et une taille d'indice constante de n = 1 000 000:

rayon	Requête OPERS.	Temps de requête
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

Pour l'essayer par vous-même, exécutez le programme de test, runmvptree2 . Vous pouvez jouer avec les paramètres de test dans le fichier, tests / run_mvptree2.cpp.

Programmation

Utilisez les fichiers d'en-tête de modèle. Créez d'abord un type de données personnalisé. Des exemples sont fournis sous clé.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);
	}
	
};

Le type de données personnalisé doit fournir le contratrice de copie, l'opérateur d'affectation et l'implémentation de la fonction de distance.

Ensuite, utilisez la classe des modèles:

 #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);

Pour plus de détails, consultez les programmes dans le répertoire des tests.

Installer

 cmake .
make
make test
make install